
ZOJ Problem Set  3227
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.
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 (x_{1}, y) to point (x_{2}, y + 1), 0 <= x < W, where d_{y} = x_{1}  x_{2} is the distance she moves in xdirection. 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:
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 kth line describe a bullet or a item at point (X_{k}, Y_{k}) by 3 integers 0 <= X_{k} < W, 0 <= Y_{k} < S and 0 < Z_{k} < 10000. A positive Z_{k} stands for a pink item, while a negative one stands a bullet. All (X_{k}, Y_{k}) 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)  Z_{1} + Z_{2} + Z_{3} + Z_{4} = 6 + (6  6 * 0)  3 + 3 + 3 + 3 = 18. External Links Author: WU, Zejun Source: ZOJ Monthly, July 2009 