Software Company

Time limit1sMemory limit128 MB

Summary

Assign m subprojects of each of two projects to n employees, who work sequentially, to minimize the largest total working time.

Level: Hard8 of 10
Topics: Binary search, Greedy, Dynamic programming, Sorting
Solved: No attempts yet

Problem

A software development company has been assigned two programming projects. Because both projects belong to the same contract, they must be delivered at the same time; finishing one earlier does not help.

The company has $n$ employees available for the work. To make the two projects easier to manage, each project is split into $m$ independent subprojects. A single subproject can be worked on by only one employee at a time, but different subprojects of the same project may be handled by different employees simultaneously.

An employee may take on several subprojects and processes them sequentially, so that employee's working time is the sum of the durations of the subprojects assigned to them. The goal is to finish both projects as early as possible — that is, to minimize the moment at which the last subproject is completed (the largest total working time among all employees).

Input

The first line contains the number of test cases $t$ ( $1 \le t \le 11$ ). The test cases follow.

The first line of each test case contains two integers $n$ ( $1 \le n \le 100$ ) and $m$ ( $1 \le m \le 100$ ). The next $n$ lines each contain two integers $x_i$ and $y_i$ : $x_i$ is the time in seconds employee $i$ needs to finish one subproject of the first project, and $y_i$ is the time in seconds the same employee needs to finish one subproject of the second project.

Output

For each test case, print on its own line a single integer: the minimum time in seconds after which both projects can be completed.

Examples3

Example 1
Input
```
1
3 20
1 1
2 4
1 6
```
Expected output
```
18
```
Example 2
Input
```
1
1 1
5 7
```
Expected output
```
12
```
Example 3
Input
```
1
2 1
10 1
1 10
```
Expected output
```
1
```