Harnessing your entrepreneurial spirit, you have decided to found a start-up. Your start-up, the first of its kind, will sell ice cream at the local beach. Every day, the beach gets ~N~ visitors which sit at specific locations on the beach. The visitors would all love to buy ice cream, but they don't like walking around in the sun. A visitor's reluctance to buy ice cream is calculated by multiplying their distance from the nearest ice cream stand by their reluctance factor: a number unique to each visitor.

You have access to ~M~ ice cream stands, which you can place anywhere on the beach. Moreover, you know where every visitor will sit and you know their reluctance factor. Since you don't want your start-up to sink, you'd like to carefully position your stands to minimize the total reluctance of all the visitors.

Can you figure out the minimum total reluctance that you can achieve?

Input Specification

The input contains ~10~ test cases.

Each test case starts with two integers ~N~ ~(1 \le N \le 4000)~, ~M~ ~(1 \le M \le 20)~ where ~N~ is the number of visitors and ~M~ is the number of ice cream stands. The next ~N~ lines describe the visitors coming to the beach. Each line contains two integers ~X~ and ~F~, where ~X~ represents the locations of the visitor on the beach and ~F~ represents the reluctance factor of that visitor ~(1 \le X, F \le 10^6)~.

Visitors will be listed in ascending order of ~X~ and no two visitors will be at the same location. Since the beach is long and thin, it can be thought of as being one dimensional.

For ~30\%~ of the cases, ~N \le 10~.
For ~60\%~ of the cases, ~N \le 100~.

Output Specification

For each test case, your program should output the minimum total reluctance of all the visitors, modulo ~1\,000\,000\,007~, or ~10^9 + 7~. *

Sample Input

2 1
10 10
20 10
2 2
10 10
20 10
4 2
1 10000
100 10
150 10
200 10

Sample Output

100
0
1000

Note: Only ~3~ cases are shown in this sample.

Explanation of Sample Output

In the first test case, it's best to put your only ice cream stand anywhere between positions ~10~ and ~20~. If we were to put it at position ~15~, then each visitor would have a reluctance of ~5 \times 10 = 50~, for a total reluctance of ~100~.

In the second test case, you can perfectly accommodate both guests by putting your two carts at locations ~10~ and ~20~.

In the last test case, it's best to put one cart at location ~1~ to appease the incredibly reluctant visitor and put your second cart at location ~150~.

Footnotes

* This means that if the minimum total reluctance is ~999\,999\,999\,999~ you should output ~999\,993\,006~, the remainder after dividing ~999\,999\,999\,999~ by ~1\,000\,000\,007~.

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org