思考题for Ep.11

Lunatic Walking

Orange Boy loves walking. One day, he wanna walk from (sx,sy) to (ex,ey)
the boy can walk in three types:

1. from (x,y) to (x\pm1,y) by costing A yuan

2. from (x,y) to (x,y\pm1) by costing B yuan

3. from (x,y) to (x+1,y+1) or (x-1,y-1) by costing C yuan

There are some exchange stations at (p_1,q_1) (p_2,q_2) .. (p_m,q_m) if he reaches station i he will get w_i yuan in return.
What's the minimal cost from start to end???!!?!

Examples

Input
A,B,C=2,3,4
(1,1) -> (4,3)
Stations:
(3,3,1)
(2,2,3)
(100,100,100)
Output
6
Explain
Path is this:
(1,1) -> (2,2) -> (3,3) -> (4,3)
Cost=4+4+2-1-3=6

Constriants

Subtask 1(100%): N \leq 10^6,0\leq A,B,C,sx,sy,ex,ey,p_i,q_i,w_i \leq 10^9