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?
Input
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 ith road (the road is twoway), t_{i} is the time in minutes required to pass the ith road, m_{i} is the weight limit for the ith road in grammes (1 ≤ a_{i}, b_{i} ≤ N; a_{i} ≠ b_{i}; 0 ≤ t_{i} ≤ 1440; 0 ≤ m_{i} ≤ 10^{9}).
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).
Output
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.
Samples
input  output 

3 3
1 2 10 3000220
2 3 20 3000201
1 3 1 3000099
 2

1 0  10000000 
Problem Author: Pavel Egorov
Problem Source: IX Urals Programming Contest. Yekaterinburg, April 1924, 2005