n processes, numbered 1..n by the order they are listed, arrive at given non-negative integer times with given positive integer CPU burst lengths. No two processes share the same arrival time. A single CPU uses ROUND-ROBIN scheduling with a fixed time quantum q:
- Processes wait in a FIFO ready queue.
- The CPU always runs the process at the front of the ready queue for
min(quantum, remaining burst)time units, then removes it from the front. - If, at the exact instant a process's time slice ends, it still has remaining burst left, it rejoins the BACK of the ready queue - but any process that arrives at that exact same instant joins the back of the queue FIRST, before the just-preempted process rejoins.
- If the ready queue is ever empty while processes remain to arrive, the CPU sits idle until the next arrival.
- A process finishes when its remaining burst reaches 0; its COMPLETION TIME is the time at which this happens, and its TURNAROUND TIME is
(completion time - arrival time).
Determine the process with the MAXIMUM turnaround time. If several processes tie for the maximum, print the SMALLEST process number among them.
Input format
Line 1: two integers n and q.
Lines 2..n+1: the i-th of these lines (1-indexed) has two integers arrival burst for process i.
Output format
A single integer: the process number with the largest turnaround time (smallest number on ties).
Constraints
- 1 <= n <= 1000
- 1 <= q <= 1000000
- 0 <= arrival <= 1000000, all arrivals distinct
- 1 <= burst <= 1000000