Aiden Pearce is one of the most famous hackers of all time, just recently he acquired a new powerful teleport that can be used exactly K times before it self-destructs.

So he decided to rob as many banks as he can from Linearland. Linearland consists of N cities on a 1-dimensional plane which Aiden can visit, after he’s teleported to some city of Linearland he can begin robbing banks, each city i has a bank that contains G_i dollars.

The teleportation device is also expensive to use; in order to teleport to some city i he has to pay T_i dollars but teleportation isn’t his only means of transport he can also visit cities by helicopter which costs W dollars per meter. Aiden's initial position is outside Linearland, so, the first city he visits can only be reached by teleportation.

Each city i is situated in position X_i (which means it’s X_i meters far from the beginning of Linearland). Aiden isn’t sure that robbing Linearland banks is profitable so he asked you to calculate the maximum amount of money he can earn.

(Aiden can have a negative amount of money at any time).

Please note that Aiden doesn't need to use all K teleports, and since he is very greedy he will never go to Linearland if his net profit is negative (i.e. if he can't get a positive profit he will settle with a good old 0).

Input

First T the number of test cases,

For each test case:

3 integers separated by space representing (1 ≤ N ≤ 10³), (1 ≤ K ≤ N) and (W ≤ 10⁹).

Then N lines each line consists of 3 integers (0 ≤ X_i ≤ 10⁹), (1 ≤ T_i ≤ 10⁹), (1 ≤ G_i ≤ 10⁹).

Output

One line per test case, each with a single integer which is the maximum amount of money.

Input:
1
4 1 1
1 1000 100
3 0 10
4 20 3
10 90 0

Output:
109