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.
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 a single integer, the maximum total quality that can be achieved without any complaints.
2 12 13 1
4
5 12 67 11 41 103 5
29
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.
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.
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 a single integer, the maximum total quality that can be achieved without any complaints.
2 12 13 1
4
5 12 67 11 41 103 5
29
5 22 67 11 41 103 5
30
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$$$.
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.
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 a single integer, the number of the visitor who makes the $$$k$$$th visit.
2 51 23 3
2
3 201 11 11 1
2
3 201 23 32 4
3
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:
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:
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.
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 a single integer, the number of the visitor who makes the $$$k$$$th visit.
2 51 23 3
2
3 201 11 11 1
2
3 201 23 32 4
3
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:
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: