E. Painting Crosswalks
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Election season has arrived in the town, and as every four years, the mayor wants to fix the public infrastructure a couple of months beforehand. This way, the city looks splendid on election day and gains the support of undecided voters.

For this election, he has decided to focus on the crosswalks. Over the years, their paint has deteriorated, so they need to be repainted. Some lines disappear completely, while others only partially... Additionally, it should be noted that after several repaints, it is likely that we will have a large number of lines, completely scattered, with different shades of faded white, which do not look very aesthetic.

But this will come to an end. The mayor has decided that he wants to repaint all the crosswalks in such a way that they all look nice. A nice crosswalk verifies the following characteristics:

  • Only the lines painted last are visible, meaning all old lines are covered.
  • The crosswalk has at most $$$k$$$ lines.
  • Each line can have any width we want (although it must be an integer), and furthermore, the width of the thickest line is as small as possible.
  • It is not necessary for the lines to be evenly spaced, and in fact, there may be no space between two adjacent lines.

As an intern in the urban planning department of the town hall, the mayor has entrusted you with the task of deciding what width the lines should have for each crosswalk to be nice.

Input

The input will start with a number $$$T$$$, the number of crosswalks we are going to paint.

Each crosswalk will begin with two numbers $$$n$$$ and $$$k$$$, the number of old visible lines in the section of road we want to paint and the maximum number of lines we are willing to paint in the new crosswalk, respectively.

Following this, there will be $$$n$$$ pairs of numbers $$$a_0$$$ $$$l_0$$$ $$$a_1$$$ $$$l_1$$$ $$$\ldots$$$ $$$a_{n-1}$$$ $$$l_{n-1}$$$. The $$$i$$$-th pair indicates the height at which the old line $$$i$$$ is located and the width of that line, respectively.

Output

For each crosswalk, an integer will be written on a separate line, indicating the maximum width that its lines can have for it to be nice.

Scoring

$$$T \leq 80$$$

$$$1 \leq n \leq 10^5$$$

$$$1 \leq k \leq 10^9$$$

$$$1 \leq a_i \leq 5 \cdot 10^8$$$, $$$a_i \neq a_j$$$ for all $$$i \neq j$$$

$$$1 \leq l_i \leq 5 \cdot 10^8$$$

15 points: $$$k \leq n \leq 100$$$, $$$a_i \leq 1000$$$, $$$l_i = 1$$$, the sum of the $$$n$$$ in all cases is less than $$$5000$$$

27 points: $$$\frac{\max(a_i+l_i)}{10} \leq k$$$, the sum of the $$$n$$$ in all cases is less than $$$10^6$$$

35 points: $$$l_i = 1$$$, the sum of the $$$n$$$ in all cases is less than $$$10^6$$$

23 points: No additional restrictions, the sum of the $$$n$$$ in all cases is less than $$$1500000$$$

Example
Input
3
3 2
1 1 4 1 10 1
5 3
2 1 5 1 9 1 13 1 11 1
2 2
3 3 2 2
Output
4
4
2