Problem: You are a manager of a prestigious soccer team in the JOI league.

The team has $N$ players numbered from 1 to $N$. The players are practicing hard in order to win the tournament game. The field is a rectangle whose height is $H$ meters and width is $W$ meters. The vertical line of the field is in the north-south direction, and the horizontal line of the field is in the east-west direction. A point in the field is denoted by ($i, j$) if it is $i$-meters to the south and $j$ meters to the east from the northwest corner of the field.

After the practice finishes, players must clear the ball. In the beginning of the clearance, the player $i$ ($1 \leq i \leq N$) stands at ($S_i, T_i$). There is only one ball in the field, and the player 1 has it. You stand at ($S_N, T_N$) with the player $N$. The clearance is finished if the ball is passed to ($S_N, T_N$), and you catch it. You cannot move during the clearance process.

You can ask players to act. But, if a player acts, his fatigue degree will be increased according to the action. Here is a list of possible actions of the players. If a player has the ball, he can act (i),(ii), or (iii). Otherwise, he can act (ii) or (iv).

* (i) Choose one of the 4 directions (east/west/south/north), and choose a positive integer $p$. Kick the ball to that direction. Then, the ball moves exactly p meters. The kicker does not move by this action, and he loses the ball. His fatigue degree is increased by $A \times p + B$.
* (ii) Choose one of the 4 directions (east/west/south/north), and move 1 meter to that direction. If he has the ball, he moves with it. His fatigue degree is increased by $C$ regardless of whether he has the ball or not.
* (iii) Place the ball where he stands. He loses the ball. His fatigue degree does not change.
* (iv) Take the ball. His fatigue degree does not change. A player can take this action only if he stands at the same place as the ball, and nobody has the ball.



Note that it is possible for a player or a ball to leave the field. More than one players can stand at the same place.

Since the players just finished the practice, their fatigue degrees must not be increased too much. You want to calculate the minimum possible value of the sum of fatigue degrees of the players for the clearance process.





Example

Input

6 5
1 3 6
3
1 1
0 4
6 5


Output

26

Solution (in CPP):

Solution:
   #include <bits/stdc++.h>
 
//    #include <boost/multiprecision/cpp_int.hpp>
 #define int long long
 #define inf  1000000007
 #define pa pair<int,int>
 #define ll long long
 #define pal pair<double,double>
 #define ppap pair<pa,int>
  #define PI 3.14159265358979323846
  #define paa pair<int,char>
  #define  mp make_pair
  #define  pb push_back
  #define EPS (1e-8)
                                          
    int dx[8]={0,1,0,-1,1,1,-1,-1};
    int dy[8]={1,0,-1,0,-1,1,1,-1};
                                            using namespace std;
                                   			class pa3{
                                            	public:
                                            	int x;
                                   				int y,z;
                                            	pa3(int x=0,int y=0,int z=0):x(x),y(y),z(z) {}
                                            	bool operator < (const pa3 &p) const{
                                            		if(x!=p.x) return x<p.x;
                                            		if(y!=p.y) return y<p.y;
                                            		 return z<p.z;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                   				bool operator > (const pa3 &p) const{
                                            		if(x!=p.x) return x>p.x;
                                            		if(y!=p.y) return y>p.y;
                                            		 return z>p.z;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator == (const pa3 &p) const{
                                            		return x==p.x && y==p.y && z==p.z;
                                            	}
                                            		bool operator != (const pa3 &p) const{
                                            			return !( x==p.x && y==p.y && z==p.z);
                                            	}
                                            
                                            };
                                            
                                            class pa4{
                                            	public:
                                            	int x;
                                            	int y,z,w;
                                            	pa4(int x=0,int y=0,int z=0,int w=0):x(x),y(y),z(z),w(w) {}
                                            	bool operator < (const pa4 &p) const{
                                            		if(x!=p.x) return x<p.x;
                                            		if(y!=p.y) return y<p.y;
                                            		if(z!=p.z)return z<p.z;
                                            		return w<p.w;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator > (const pa4 &p) const{
                                            		if(x!=p.x) return x>p.x;
                                            		if(y!=p.y) return y>p.y;
                                            		if(z!=p.z)return z>p.z;
                                            		return w>p.w;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator == (const pa4 &p) const{
                                            		return x==p.x && y==p.y && z==p.z &&w==p.w;
                                            	}
                                            		
                                            
                                            };
                                            class pa2{
                                            	public:
                                            	int x,y;
                                            	pa2(int x=0,int y=0):x(x),y(y) {}
                                            	pa2 operator + (pa2 p) {return pa2(x+p.x,y+p.y);}
                                            	pa2 operator - (pa2 p) {return pa2(x-p.x,y-p.y);}
                                            	bool operator < (const pa2 &p) const{
                                            		return y != p.y ? y<p.y: x<p.x;
                                            	}
                                            	bool operator > (const pa2 &p) const{
                                            		return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator == (const pa2 &p) const{
                                            		return abs(x-p.x)==0 && abs(y-p.y)==0;
                                            	}
                                            	bool operator != (const pa2 &p) const{
                                            		return !(abs(x-p.x)==0 && abs(y-p.y)==0);
                                            	}
                                            		
                                            
                                            };
                                            
 
                      
                                string itos( int i ) {
                                ostringstream s ;
                                s << i ;
                                return s.str() ;
                                }
                                 
                                int gcd(int v,int b){
                                	if(v==0) return b;
                                	if(b==0) return v;
                                	if(v>b) return gcd(b,v);
                                	if(v==b) return b;
                                	if(b%v==0) return v;
                                	return gcd(v,b%v);
                                }
                 
                            
                                int mod;
int extgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = extgcd(b, a%b, y, x);
    y -= a/b * x;
    return d;
}
pa operator+(const pa & l,const pa & r) {   
    return {l.first+r.first,l.second+r.second};                                    
}    
pa operator-(const pa & l,const pa & r) {   
    return {l.first-r.first,l.second-r.second};                                    
}  
                                
                int pr[10000100];
                int inv[10000010];
                
                int beki(int wa,int rr,int warukazu){
                	if(rr==0) return 1%warukazu;
                	if(rr==1) return wa%warukazu;
                	wa%=warukazu;
                	if(rr%2==1) return ((ll)beki(wa,rr-1,warukazu)*(ll)wa)%warukazu;
                	ll zx=beki(wa,rr/2,warukazu);
                	return (zx*zx)%warukazu;
                }
 
                
    			int comb(int nn,int rr){
    				if(rr<0 || rr>nn || nn<0) return 0;
    				int r=pr[nn]*inv[rr];
    				r%=mod;
    				r*=inv[nn-rr];
    				r%=mod;
    				return r;
    			}
               
                void gya(int ert){
                	pr[0]=1;
                	for(int i=1;i<=ert;i++){
                		pr[i]=(pr[i-1]*i)%mod;
                	}
                		inv[ert]=beki(pr[ert],mod-2,mod);
                	for(int i=ert-1;i>=0;i--){
                		inv[i]=inv[i+1]*(i+1)%mod;
                	}
                }
                
              //   cin.tie(0);
    		//	ios::sync_with_stdio(false);
    			//priority_queue<pa3,vector<pa3>,greater<pa3>> pq;            
                 //sort(ve.begin(),ve.end(),greater<int>());
 //   mt19937(clock_per_sec);
  //  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()) ;


int dis[510][510]={};
int memo[510][510][3]={};
//bool vis[510][510][2]={};

signed main(){
	
	
   cin.tie(0);
	ios::sync_with_stdio(false);

int h,w;
	cin>>h>>w;
	const int inff=inf*100000000ll;
	for(int i=0;i<=500;i++)for(int j=0;j<=500;j++)dis[i][j]=inf,memo[i][j][0]=inff,memo[i][j][1]=inff,memo[i][j][2]=inff;
	int a,b,c;
	cin>>a>>b>>c;
	queue<pa3> qu;
	int n;
	cin>>n;
	int gx,gy;
	priority_queue<pa4,vector<pa4>,greater<pa4>> pq;  
	for(int i=0;i<n;i++){
		int x,y;
		cin>>x>>y;
			qu.push((pa3){x,y,b});
		if(i==0){
				pq.push((pa4){0,x,y,0});
			memo[x][y][0]=0;
		
		}
		if(i==n-1){
			gx=x,gy=y;
		}
	}
	while(qu.size()){
		pa3 z=qu.front();
		qu.pop();
		if(dis[z.x][z.y]!=inf) continue;
		dis[z.x][z.y]=z.z;
	//	cout<<z.x<<" "<<z.y<<"  "<<z.z<<endl;
		for(int r=0;r<4;r++){
			int X=z.x+dx[r];
			int Y=z.y+dy[r];
			
				if(X>=0 && Y>=0 && X<=h && Y<=w)qu.push((pa3){X,Y,z.z+c});
		}
	}
	
	int cnt=0;
	//for(int i=0;i<10;i++)for(int j=0;j<10;j++)cout<<dis[i][j]<<endl;
	while(pq.size()){
		pa4 z=pq.top();
		pq.pop();
		
		if(memo[z.y][z.z][z.w]<z.x)continue;
	//	cout<<z.y<<" "<<z.z<<" "<<z.w<<"   "<<z.x<<endl;
		//cnt++;
		if(z.y==gx&& z.z==gy && z.w==0){
			cout<<z.x<<endl;
			return 0;
		}
		if(z.w==0){
			for(int r=0;r<4;r++){
				int X=z.y+dx[r],Y=z.z+dy[r];
				if(X>=0 && X<=h && Y>=0 && Y<=w){
					if(memo[X][Y][0]>z.x+c){
							pq.push(pa4({z.x+c,X,Y,0}));
						memo[X][Y][0]=z.x+c;
					}
				}
			}
			for(int r=1;r<3;r++)if(memo[z.y][z.z][r]>z.x){
					pq.push((pa4){z.x,z.y,z.z,r});
				memo[z.y][z.z][r]=z.x;
			}
		}
		
		if(z.w==1){
			for(int r=0;r<4;r++)if(dy[r]==0){
				int X=z.y+dx[r],Y=z.z+dy[r];
				if(X>=0 && X<=h && Y>=0 && Y<=w){
					if(memo[X][Y][1]>z.x+a){
							pq.push(pa4({z.x+a,X,Y,1}));
						memo[X][Y][1]=z.x+a;
					}
				}
			}
			
			for(int r=0;r<1;r++)if(memo[z.y][z.z][r]>z.x+dis[z.y][z.z]){
					pq.push((pa4){z.x+dis[z.y][z.z],z.y,z.z,r});
				memo[z.y][z.z][r]=z.x+dis[z.y][z.z];
			}
		}
		
		
		if(z.w==2){
			for(int r=0;r<4;r++)if(dx[r]==0){
				int X=z.y+dx[r],Y=z.z+dy[r];
				if(X>=0 && X<=h && Y>=0 && Y<=w){
					if(memo[X][Y][2]>z.x+a){
							pq.push(pa4({z.x+a,X,Y,2}));
						memo[X][Y][2]=z.x+a;
					}
				}
			}
			//int r=0;
			for(int r=0;r<1;r++)if(memo[z.y][z.z][r]>z.x+dis[z.y][z.z]){
					pq.push((pa4){z.x+dis[z.y][z.z],z.y,z.z,r});
				memo[z.y][z.z][r]=z.x+dis[z.y][z.z];
			}
		}
		
		
		
	}
	cout<<min(memo[gx][gy][0],memo[gx][gy][1])<<endl;
	
	return 0;
	

 
 }