### Delicious Apples

Time Limit: 3000 ms
Memory Limit: 65536 KiB

#### Problem Description

There are n apple trees planted along a cyclic road, which is L metres long. Your storehouse is built at position 0 on that cyclic road.

Thei th tree is planted at position xi , clockwise from position 0 . There are ai delicious apple(s) on the i th tree.

You only have a basket which can contain at mostK apple(s). You are to start from your storehouse, pick all the apples and carry them back to your storehouse using your basket. What is your minimum distance travelled?

1≤n,k≤105,ai≥1,a1+a2+...+an≤105

1≤L≤109

0≤x[i]≤L

There are less than 20 huge testcases, and less than 500 small testcases.

The

You only have a basket which can contain at most

There are less than 20 huge testcases, and less than 500 small testcases.

#### Input

First line: t , the number of testcases.

Thent testcases follow. In each testcase:

First line contains three integers,L,n,K .

Nextn lines, each line contains xi,ai .

Then

First line contains three integers,

Next

#### Output

Output total distance in a line for each testcase.

#### Sample Input

2 10 3 2 2 2 8 2 5 1 10 4 1 2 2 8 2 5 1 0 10000

#### Sample Output

18 26

#### Hint

#### Source

2015 Multi-University Training Contest 2