ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Championship 2005 Round I

About     Problems     Submit solution     Judge status     Standings
Contest is over

J. Cups Transportation

Time limit: 1.0 second
Memory limit: 64 MB
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 ≤ MN · (N − 1) / 2). The next M lines contain information about the roads. Each road is described in a separate line with integers ai, bi, ti, mi, where ai and bi are the road map nodes connected by the i-th road (the road is two-way), ti is the time in minutes required to pass the i-th road, mi is the weight limit for the i-th road in grammes (1 ≤ ai, biN; aibi; 0 ≤ ti ≤ 1440; 0 ≤ mi ≤ 109).
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

inputoutput
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 19-24, 2005
To submit the solution for this problem go to the Problem set: 1379. Cups Transportation