The transport system of the city of Föràg consists of stations and two-way trains connecting the stations, the th of which takes minutes go from station to station or from station to station . Konajya is currently near station after visiting the Föràgian War Museum. However, she wants to go visit the Lastrevia cultural festival which is conveniently going to be held directly beside station in minutes. To use the Föràgian transport system, Konajya must first buy a transport pass. There are levels of passes, the th of which gives access to the first trains in the order given in the input statement. Help Konajya find the minimum level of the transport pass that she must buy to reach the cultural festival before it starts! (You may assume the time needed to get to the station and to buy the pass is negligible)
In all subtasks,
Subtask 1 [15%]
Subtask 2 [85%]
No additional constraints.
The first line contains two integers, and .
lines will follow. The th of these will contain the integers , and .
The last line will contain three more integers, , , and .
Output the minimum level of the Föràgian transport pass that Konajya must get so that she can get from station to station in less than minutes. If this is not possible print
4 4 1 4 10 1 2 3 3 4 2 2 3 1 1 4 9