2017 North American Practice Contest 02

Start

2017-09-24 19:00 CEST

2017 North American Practice Contest 02

End

2017-09-25 00:00 CEST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -391 days 14:00:10

5:00:00

0:00:00

Problem ATravelling Delivery Person

Frederic Edward Xavier runs a very successful delivery company called FredEX. He’s been looking at driving records lately, and is not happy with the costs of delivery.

He has made the following estimations:

• Driving from one intersection to the neighboring one costs $B$ dollars

• Going straight through an intersection costs $S$ dollars

• Turning right in an intersection costs $R$ dollars

• Turning left in an intersection costs $L$ dollars

• Delivering a package is free, but you still pay the cost for the turn/going straight in that intersection.

FredEX operates in a city where the streets make up an infinite grid of square blocks, with intersections numbered from $(-\infty ,-\infty )$ to $(\infty ,\infty )$. Lower numbers on the $x$ axis are to the left, and lower numbers on the $y$ axis are down. The truck starts at the intersection $(0, 0)$ but you may choose which direction it should face. There are $N$ packages that must be delivered in a specific order. The truck cannot go in reverse, and cannot perform U-turns to go back the way it came. Help Frederic find out the cheapest way to deliver all $N$ packages.

Input

The first line of the input is a line with five space-separated integers $B$, $S$, $R$, $L$ and $N$.

Then follow $N$ lines, each with two space-separated integers $X_ i$ and $Y_ i$, the $x$ and $y$ coordinates of the intersection for delivering package number $i$. The packages are listed in the order they must be delivered.

Output

Output the minimum cost of delivering all packages.

Limits

• $1 \leq S, R, L, B \leq 100$

• $1 \leq N \leq 30\, 000$

• $-5 \leq X_ i, Y_ i \leq 5$

Sample Input 1 Sample Output 1
1 1 1 10 2
2 2
1 2
14