Problem Description

There are $n$ balloons tied to a flat ground. Their initial height is $0$ meters, and the initial time is the $0$-th second.

After the rope of a balloon is cut, it will rise at a constant speed. The $i$-th balloon rises $v_i$ meters per second.

Now it is known that the rope of the $i$-th balloon will be cut at the $t_i$-th second. Find the index of the balloon with the greatest height at the $T$-th second; if there are multiple, output the smallest index among them.

Input Format

The first line contains two integers $n, T$.

The next $n$ lines: the $i$-th line contains two integers $v_i, t_i$.

Output Format

Output one integer in one line, representing the answer.

5 10
1 1
2 3
3 7
5 4
3 3

4

20 131
872 127
228 17
273 66
306 78
636 107
878 110
1141 122
835 10
247 28
248 48
65 4
664 109
267 96
1103 87
725 83
231 119
671 58
825 52
391 47
573 100

8

Hint

[Sample 1 Explanation]

At the $10$-th second, the heights of the five balloons are $9, 14, 9, 30, 21$ meters, respectively.

[Constraints]

For $100\%$ of the testdata, it is guaranteed that $1 \le n, v_i \le 10^5$, and $0 \le t_i \le T \le 10^4$.

Hint: This problem enables bundled tests.

$$\def\r{\cr\hline} \def\None{\text{None}} \def\arraystretch{1.5} \begin{array}{c|c|c} \textbf{Subtask} & \textbf{Sp. Constraints} & \textbf{Score}\r \textsf1& n \le 1000 & 33 \r \textsf2& v_i\ 相等 & 10 \r \textsf3& t_i \ 相等 & 10 \r \textsf4& 无特殊限制 & 47 \r \end{array}$$

Source

Item	Person
idea	EstasTonne
data
check	Chuanjiang Mowang
solution	EstasTonne

Translated by ChatGPT 5