In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
Peter is coming back from Switzerland for the finals of Algorithmic Engagements. He is planning to get there by car. The main part of his journey is driving along a newly built Polish highway - . Peter is planning to enter the highway on the 'th kilometer and exit on the 'th kilometer (). Peter's car can go with the top speed of kilometers per hour. Peter's car can change speed instantly.
Peter loves to drive fast. If he drives kilometers with the speed , his satisfaction increases by . He would like to drive along in such way that his satisfaction at the end of his journey is maximized.
Unfortunately, there are speed limits on the highway. 'th speed limit applies from the kilometer till kilometer - within this range it is not possible to drive faster than kilometers per hour. In case there are many speed limits that apply for a given segment of the highway, it is required to obey all of them.
Peter has some friends. They obligated themselves to help Peter by silently removing one of the speed limits from the highway. Peter would like to determine which speed limit to remove, so that his satisfaction can be maximized. Help him!
Write a program which:
The first line of the input contains four integers , , , : , , , separated by single spaces. Each of the following lines contains a description of one speed limit. 'th of the lines contains three integers and , separated by single spaces and representing adequately the first and the last kilometer where the speed limit applies and the speed limit itself (in kilometers per hour).
The first and only line of output should contain one integer, representing the number of the speed limit, which should be removed. Speed limits are numbered from to in the order defined by the input data. If there are many speed limits that can be removed resulting in maximized Peter's satisfaction, your program should output the speed limit that appears as the first one in the input data.
For the input data:
2 10 20 200 10 15 80 10 13 40
the correct result is:
Task author: Jakub Radoszewski (formulation by Marcin Pilipczuk).