Description

Input

The first line of input consists of two space-separated integers $n$ ($1 \le n \le 1,000,000$) and $k$ ($1 \le k \le \textcolor{red}{1,000,000}$), representing the number of visitors and the visit number to be awarded the prize.

$n$ lines follow, the $i$th of which consists of two space-separated integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le \textcolor{red}{1,000}$), representing the day of visitor $i$'s first visit and the number of days until each subsequent visit.

Output

Output a single integer, the number of the visitor who makes the $k$th visit.

2 5
1 2
3 3

3 20
1 1
1 1
1 1

3 20
1 2
3 3
2 4

2

2

3

Note

In the first sample case there are two people who visit on days $1, 3, 5, 7, \ldots$ and $3, 6, 9, 12, \ldots$ respectively. Therefore the visits are as follows:

1. day 1, by person 1
2. day 3, by person 1
3. day 3, by person 2
4. day 5, by person 1
5. day 6, by person 2,

so person 2 gets the prize.

In the second sample case three people each visit the site every day. The first six days see 18 visits, then the three people visit the site on day 7 in order. Therefore person 1 makes the nineteenth visit and person 2 gets the prize.

In the third sample case there are three people:

• person 1 visits on days $1, 3, 5, 7, \ldots$
• person 2 visits on days $3, 6, 9, 12, \ldots$
• person 3 visits on days $2, 6, 10, 14, \ldots$.

The twentieth visit is made by person 3, so they win the prize.