「單調遞增遲到資訊學競賽」（MITIT）的河狸主辦人們需要定期開會以確保競賽順利進行，但他們有時會失去動力。

共有 $N$ 位河狸主辦人，他們定期召開會議，每次會議持續的時間恰好為 $M$ 分鐘。第 $i$ 位河狸在第一次會議時遲到了 $t_i$ 分鐘。在隨後的每一次會議中，第 $i$ 位河狸會比上一次會議多遲到 $a_i$ 分鐘。請輸出第一次所有人都遲到以至於錯過整場會議的會議編號。

若一位河狸遲到的時間達到 \textbf{至少} $M$ 分鐘，則稱其錯過了整場會議。

Input

第一行包含兩個以空格分隔的整數 $N$ ($ 1 \le N \le 2\cdot 10^5$) 與 $M$ ($ 1 \le M \le 10^9$)。

接下來 $N$ 行中的第 $i$ 行包含兩個整數 $t_i$ ($0 \le t_i < M$) 與 $a_i$ ($1 \le a_i \le 10^9$)。

Output

輸出一行，包含答案。

Example

Input

4 60
0 9
30 4
10 12
14 9

Output

9

Notes

在第一次會議中，第 $1$ 位河狸準時到達，第 $2$ 位河狸遲到 $30$ 分鐘，第 $3$ 位河狸遲到 $10$ 分鐘，第 $4$ 位河狸遲到 $14$ 分鐘。在第 $9$ 次會議中，第 $1$ 位河狸遲到 $72$ 分鐘，第 $2$ 位河狸遲到 $62$ 分鐘，第 $3$ 位河狸遲到 $106$ 分鐘，第 $4$ 位河狸遲到 $86$ 分鐘。這是第一次所有人都遲到至少 $60$ 分鐘的會議；而在第 $8$ 次會議中，第 $2$ 位河狸僅遲到 $58$ 分鐘。