HACK14 - The Hack

 

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. Aidens initial position is outside Linearland, so, the first city he visits can only be reached by teleportaion.
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).

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; inn 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. Aidens initial position is outside Linearland, so, the first city he visits can only be reached by teleportaion.

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^3), (1 <= K <= N) and (W <= 10^9).

Then N lines each line consists of 3 integers (0 <= X[i] <= 10^9), (1 <= T[i] <= 10^9), (1 <=  G[i] <= 10^9).

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

Added by:Aleksandar Abas
Date:2014-10-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:Own Problem used for KCPC 2014

hide comments
2015-01-21 14:36:27 :D
Can the result ever be negative? Do you have to use the teleport at lease once or exactly K times?
--Francky--> Email sent to psetter.
UPD: I updated the statement to answer both of your questions :D

Re: Thanks, maybe I'll revisit the problem.

Last edit: 2015-02-16 15:38:13
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.