Restroom Rules

Deka wants to use the company restroom. However, a plumbing failure has banned the use of every restroom in the company, so the employees have to use a single temporary restroom.

N employees, Deka among them, are waiting in front of the temporary restroom. Deka stands K + 1-th in the line of N people. In other words, K people arrived before Deka. As the line grew long, the boss ordered everyone to split into M lines.

The N employees split into M lines in order. The 1st employee of the original line goes to line 1, the 2nd employee to line 2, ..., the M-th employee to line M, and the M + 1-th employee goes behind line 1.

Seeing the split into M lines, the boss was very satisfied and left.

The employees in the M lines implicitly agreed to use the restroom according to the following rules.

• The head is the person in a line who arrived first and stands at the front.
• Among the heads of the M lines, the head with the highest number of days worked Di uses the restroom.
• If two or more heads of the M lines share the highest number of days worked Di, the head among them with the highest urgency level Hi uses the restroom.
• If two or more heads of the M lines share the highest number of days worked Di and also share the same urgency level Hi, the head among them in the line with the lowest line number uses the restroom.

After how many employees use the restroom does Deka's turn come? Let us calculate it for Deka, who is starting to get very anxious.

The first line gives the number of employees waiting at the temporary restroom N (1 ≤ N ≤ 105), the number of new lines ordered by the boss M (2 ≤ M ≤ 105), and the number of employees standing in front of Deka when he arrived at the restroom K (0 ≤ K ≤ N − 1), separated by spaces.

From the second line, each of the N lines gives the number of days worked Di (0 ≤ Di ≤ 36,500) and the integer Hi (0 ≤ Hi ≤ 108) representing the urgency level of the employee who stood i-th in line at the temporary restroom, from the employee who arrived first, separated by spaces.

Print how many employees use the restroom before Deka uses it.

Consider the case where the line is formed as above. (x, y) means the employee's number of days worked is x and urgency level is y. [x, y] means that employee is Deka. That is, in the picture above, Deka is employee 3.

Here the number of waiting employees N is 6. Two people stand in front of Deka, so K is 2. If the boss orders everyone to split into 3 lines,

they can split as above. Here Deka is the head of line 3.

Now let us see which heads use the restroom.

In this case the head of line 1, who has the highest number of days worked, uses the restroom.

The heads of lines 1 and 2 have the same number of days worked, 1,500, but the head of line 2 has the higher urgency level, so the head of line 2 uses the restroom.

The heads of lines 1 and 2 have the same number of days worked, 1,500, and the same urgency level, 100, but line 1 has the lower line number, so the head of line 1 uses the restroom.

The head of line 2 has the highest number of days worked, so he uses the restroom.

The head of line 3 has the highest number of days worked, and this employee is Deka, so the answer is to print 4, the number of employees in the line who used the restroom before Deka.