In Gensokyo, people relax and bask in the calm of a winter without end. Spring has shown no sign of arriving even though it's already May, and in fact the snowstorms are continually getting worse. Kirisame Marisa, a playful magician, sees a cherry blossom petal float down outside her warm house and wonders if spring is happening somewhere else. She follows the trail of cherry blossoms high above Gensokyo, eventually crosses a great magical boundary into the Netherworld. At the end of a long journey, she comes face to face with Saigyouji Yuyuko, the ghost princess of Hakugyokurou, who had been stealing the essence of "spring" throughout Gensokyo in order to make the Saigyou Ayakashi, a youkai cherry tree, bloom perfectly with the rest of Hakugyokurou's gardens. And Marisa defeats her to reclaim Gensokyo's spring.
perfect_cherry_blossom_0.jpg
Assume that Marisa starts the journey at any point of line y=-1 and ends at line y=S. After each unit time, she can move from point (x1, y) to point (x2, y + 1), 0 <= x < W, where dy = |x1 - x2| is the distance she moves in x-direction. If Marisa appears in the same point with a bullet or a item, then she will be struck by the bullet or get the item, respectively. Marisa's aim is to get as many cherry points as possible during the journey. There are many things linking with the cherry points:
When Marisa starts off her journey, she has 0 cherry points;
Shooting enemies increases Marisa's cherry points, she can gain at most B cherry points in total in this way, where B is a given constant;
Being struck by bullets decreases Marisa's cherry points by a certain number |zi| for each bullet;
Gathering pink items (cherry blossom petals) increases Marisa's cherry points by a certain number |zj| for each item;
Grazing bullets by having them pass through her sprite but not her hitbox increases Marisa's cherry points. But it's not an easy job, especially when she has to move in x-direction to avoid bullets or gather items. She can gain at most C - A * d (maybe negative, it's valid) cherry points in total in this way, where C and A are constants, d is the total distance she moves in x-direction. This means that the more Marisa moves in x-direction, the less cherry points she can gain.
Marisa wants to know how many cherry points she can get at most.
Input
There are no more than 100 cases, most of which are small ones. Process to the end of file.
Each case begins with 6 integers 1 <= W <= 30000, 1 <= S <= 900000000, 0 <= N <= 60000, 0 <= A <= 10, 0 <= B <= 100000000 and 0 <= C <= 1000000000. Then N lines. The k-th line describe a bullet or a item at point (Xk, Yk) by 3 integers 0 <= Xk < W, 0 <= Yk < S and 0 < |Zk| < 10000. A positive Zk stands for a pink item, while a negative one stands a bullet. All (Xk, Yk) are different.
Output
The maximum possible cherry points on separate lines.
Sample Input
2 3 3 0 0 0
0 0 -1
1 1 -1
0 2 -1
6 6 6 6 6 6
3 0 -3
3 1 3
3 2 3
3 3 3
2 3 4
4 3 2
Sample Output
0
18
Hint
A possible strategy for sample 1: (0, -1)->(1, 0)->(0, 1)->(1, 2)->(0, 3), and the cherry points will be B + (C - A * d) = 0 + (0 - 0 * 4) = 0.
A possible strategy for sample 2: (3, -1)->(3, 0)->(3, 1)->(3, 2)->(3, 3)->(3, 4)->(3, 5)->(3, 6), and the cherry points will be B + (C - A * d) - |Z1| + |Z2| + |Z3| + |Z4| = 6 + (6 - 6 * 0) - 3 + 3 + 3 + 3 = 18.
External Links
