It was decided to prepare specially designed cups with a competition logotype of Ural Championship 2005 for each participant and for any observer, who wish to have such a cup.

Having a habit to do such important things at the last moment, designer finished his job with a cup design two days before the Championship. So there is a shortage of time. One day is needed to manufacture the cups and to put Championship logotype onto them. So there are 24 hours left to deliver the cups from an enterprise to contest area.

Maybe, it is impossible to deliver all ten million cups (this is the amount of cups ordered by organizing committee) in a one trip. But it is desirable to deliver as many of cups as possible in a one trip.

Organizing committee ordered one big delivery truck. One would try to load the truck by the cups for it's full load. But some roads have weight limit: if the weight of the truck exceeds the road weight limit, it can not pass the road. So it is possible, that fully loaded truck can not go along the shortest route of delivery, it has to use longer route with acceptable weight limit. Moreover, it is possible, that the fully loaded truck will not deliver the cups in time. And it is definitely unacceptable.

So, how many cups can be loaded into the truck, so that this precious load could be delivered in 24 hours without violation of road weight limits?

The first line contains integers N and M that are the total number of the road map nodes and the total number of the roads (1 ≤ N ≤ 500; 0 ≤ M ≤ N · (N − 1) / 2). The next M lines contain information about the roads. Each road is described in a separate line with integers a_i, b_i, t_i, m_i, where a_i and b_i are the road map nodes connected by the i-th road (the road is two-way), t_i is the time in minutes required to pass the i-th road, m_i is the weight limit for the i-th road in grammes (1 ≤ a_i, b_i ≤ N; a_i ≠ b_i; 0 ≤ t_i ≤ 1440; 0 ≤ m_i ≤ 10⁹).

For any two road map nodes there is at most one road connecting them. The enterprise, where the cups are manufactured, is placed in a node 1. The Urals Championship area is placed in a node N. One cup has a weight of 100 grammes, and the empty truck has a weight of 3000 kilogrammes (1 kilogramme = 1000 grammes).

Print the only number: the total amount of the cups (it must be as much as possible), which can be delivered in the first trip of the truck in a time of 24 hours.