#P10920. [2015杭电多校]Delicious Apples

    ID: 10062 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 6 上传者: 标签>CF2100提高排序贪心交换论证线性 DP暴力枚举固定一个变量消去另一维

[2015杭电多校]Delicious Apples

Delicious Apples

Problem Description

There are nn apple trees planted along a cyclic road, which is LL metres long. Your storehouse is built at position 00 on that cyclic road. The iith tree is planted at position x_i, clockwise from position 00. There are aia_i delicious apple(s) on the iith tree. You only have a basket which can contain at most KK 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\le n,k\le 10^5, a_i\ge 1, a_1+a_2+...+a_n\le 10^5$ 1≤L≤1091\le L\le 10^9 0≤x[i]≤L0\le x[i]\le L There are less than 20 huge testcases, and less than 500 small testcases.

Input

First line: tt, the number of testcases. Then tt testcases follow. In each testcase: First line contains three integers, L,n,KL,n,K. Next nn lines, each line contains xi,aix_i,a_i.

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

Author

XJZX

Source

2015 Multi-University Training Contest 2