COMP4128 23T3 Contest 2
A1. Project Allocation (Subtask)
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Marta has two employees named Arda and Bimala. For each of the next $$$n$$$ days, she will receive a project and must choose which employee to assign it to. Arda and Bimala will complete the $$$i$$$th project with quality $$$a_i$$$ and $$$b_i$$$ respectively. However, if at any point either employee is assigned more than $$$k$$$ projects more than their colleague, they will complain that the allocation is unfair.

Help Marta decide the maximum total quality that her team can achieve without complaints.

Input

The first line of input consists of two space-separated integers $$$n$$$ ($$$1 \le n \le 1000$$$) and $$$k$$$ ($$$\color{red}{k = 1}$$$), representing the number of projects and the largest tolerable difference in the number of projects assigned to each employee.

$$$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 {10}^6$$$), representing the quality of Arda's and Bimala's work respectively for task $$$i$$$.

Output

Output a single integer, the maximum total quality that can be achieved without any complaints.

Examples
Input
2 1
2 1
3 1
Output
4
Input
5 1
2 6
7 1
1 4
1 10
3 5
Output
29
Note

In the first sample case Arda would produce better quality for either project, but he will complain if he is assigned the first two projects at which point Bimala has none. Therefore Bimala should be assigned project 1 and Arda project 2, for a total quality of 4.

In the second sample case Arda can be given projects 2 and 3, and Bimala projects 1, 4 and 5, for a total quality of $$$6 + 7 + 1 + 10 + 5 = 29$$$. At no point does either employee have more than one project more than their colleague.

A2. Project Allocation (Full)
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Marta has two employees named Arda and Bimala. For each of the next $$$n$$$ days, she will receive a project and must choose which employee to assign it to. Arda and Bimala will complete the $$$i$$$th project with quality $$$a_i$$$ and $$$b_i$$$ respectively. However, if at any point either employee is assigned more than $$$k$$$ projects more than their colleague, they will complain that the allocation is unfair.

Help Marta decide the maximum total quality that her team can achieve without complaints.

Input

The first line of input consists of two space-separated integers $$$n$$$ ($$$1 \le n \le 1000$$$) and $$$k$$$ ($$$\color{red}{1 \le k \le n}$$$), representing the number of projects and the largest tolerable difference in the number of projects assigned to each employee.

$$$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 {10}^6$$$), representing the quality of Arda's and Bimala's work respectively for task $$$i$$$.

Output

Output a single integer, the maximum total quality that can be achieved without any complaints.

Examples
Input
2 1
2 1
3 1
Output
4
Input
5 1
2 6
7 1
1 4
1 10
3 5
Output
29
Input
5 2
2 6
7 1
1 4
1 10
3 5
Output
30
Note

In the first sample case Arda would produce better quality for either project, but he will complain if he is assigned the first two projects at which point Bimala has none. Therefore Bimala should be assigned project 1 and Arda project 2, for a total quality of 4.

In the second sample case Arda can be given projects 2 and 3, and Bimala projects 1, 4 and 5, for a total quality of $$$6 + 7 + 1 + 10 + 5 = 29$$$. At no point does either employee have more than one project more than their colleague.

In the third sample case Arda can be given projects 2 and 5, and Bimala projects 1, 3 and 4, for a total quality of $$$6 + 7 + 4 + 10 + 3 = 30$$$. Note that while the overall allocation gives Bimala only one more project than Arda, she would still complain if $$$k$$$ was 1 rather than 2, since after the first four projects she has three while Arda only has one.

Note that the third sample case is not a valid input for the subtask, as $$$k \gt 1$$$.

Statement is not available in English language
Statement is not available in English language
C1. One Millionth Visitor (Subtask)
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Nadja has a website where she posts motivational quotes. There are $$$n$$$ visitors to her website, the $$$i$$$th of which makes their first visit on day $$$a_i$$$ and returns every $$$b_i$$$ days thereafter. If several people visit her website on the same day, they do so in the order of their visitor number (i.e. their order in the input).

Nadja wants to give a special prize to mark the $$$k$$$th visit to her website. Help her determine who should be given the prize.

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 \color{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 \color{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.

Examples
Input
2 5
1 2
3 3
Output
2
Input
3 20
1 1
1 1
1 1
Output
2
Input
3 20
1 2
3 3
2 4
Output
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.

C2. One Millionth Visitor (Full)
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Nadja has a website where she posts motivational quotes. There are $$$n$$$ visitors to her website, the $$$i$$$th of which makes their first visit on day $$$a_i$$$ and returns every $$$b_i$$$ days thereafter. If several people visit her website on the same day, they do so in the order of their visitor number (i.e. their order in the input).

Nadja wants to give a special prize to mark the $$$k$$$th visit to her website. Help her determine who should be given the prize.

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 \color{red}{1,000,000,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 \color{red}{1,000,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.

Examples
Input
2 5
1 2
3 3
Output
2
Input
3 20
1 1
1 1
1 1
Output
2
Input
3 20
1 2
3 3
2 4
Output
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.