#681. 【UR #22】月球列车

样例一

input

2 2 0
1 2
2
3



output

7
1



限制与约定

1 $10^3$ $1$ $30$
2 $10^5$ $1$ $30$
3 $2.5\times 10^5$ $0$ $30$
4 $2.5\times 10^5$ $1$ $10$