For the next Summer Computer School, it was decided to prepare circles for both schoolchildren and all teachers.
Having a habit of doing important things at the very last moment, the designer finished the layout two days before school started. It will take another day for the manufacturer to make mugs and put an image on them. It only takes 24 hours for NATO to take the mugs from the factory to LKSH.
An order for 10,000,000 mugs (namely, that's how many the organizers ordered), of course, cannot be taken away in one flight. However, for the first flight I want to bring the maximum number of mugs. One heavy truck was ordered for transportation. But there is one caveat: on some roads there is a limit on the weight of the car. Therefore, if the car is loaded with mugs to the eyeballs, then it may not be possible to use the shortest route, but you will have to take a detour. It may even happen that because of this, the truck will not have time to reach the camp on time, and this cannot be allowed. So, how many mugs can be loaded into the car in order to have time to bring this valuable cargo on time, and without violating the rules of the road?
Input
The first line contains the numbers n (1≤n≤500) and m - the number of nodes in the road map and the number of roads, respectively. The next m lines contain information about the roads. Each road is described on a separate line as follows. First, the numbers of the junction points that are connected by this road are given, then the time it takes to travel along this road, and finally, the maximum weight of a car that is allowed to drive on this road. It is known that all roads connect different points, and for each pair of points there is at most one road directly connecting them. All numbers are separated by one or more spaces.
Nodal points are numbered from 1 to n. At the same time, the plant for the production of mugs has number 1, and LKSH - number n. Travel time on the road is given in minutes and does not exceed 1440 (24 hours). The mass limit is given in grams and does not exceed one billion. In addition, it is known that one mug weighs 100 grams, and an empty truck - 3 tons.
Output
Print a single number - the maximum number of mugs that can be brought on the first flight, spending no more than 24 hours.
Examples
| # |
Input |
Output |
| 1 |
3 3
1 2 10 3000220
2 3 20 3000201
1 3 1 3000099
|
2 |