思考题for Ep.11

Lunatic Walking

Orange Boy loves walking. One day, he wanna walk from to

the boy can walk in three types:

  1. from to by costing A yuan

  2. from to by costing B yuan

  3. from to or by costing C yuan

There are some exchange stations at .. if he reaches station i he will get 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%):