infinite grid with tunnels where cost is K
#include<bits/stdc++.h>
using namespace std;
#define int long long int
const int N = 402;
int dp[N][N];
pair<int,int> g[N];
int dist[N];
bool vis[N];
int32_t main(){
int k,a,b,c,d,n,p,q,r,s,index,nodes,val;
cin>>k>>a>>b>>c>>d>>n;
index = 2;
nodes = 2*n+1;
for(int i=1;i<=nodes;i++)
dist[i] = INT_MAX;
memset(vis,false,sizeof(vis));
memset(dp,-1,sizeof(dp));
for(int i=0;i<=nodes;i++)
dp[i][i] = 0;
g[0] = {a,b};
g[1] = {c,d};
dp[0][1] = dp[1][0] = abs(a-c)+abs(b-d);
for(int i=0;i<n;i++){
cin>>p>>q>>r>>s;
dp[index][index+1] = k;
dp[index+1][index] = k;
g[index] = {p,q};
g[index+1] = {r,s};
for(int j=0;j<index;j++){
val = abs(p-g[j].first)+abs(q-g[j].second);
dp[j][index] = dp[index][j] = val;
val = abs(r-g[j].first)+abs(s-g[j].second);
dp[j][index+1] = dp[index+1][j] = val;
}
index += 2;
}
for(int i=0;i<=nodes;i++){
int v = -1;
for(int j=0;j<=nodes;j++){
if(!vis[j] && (v == -1 || dist[j] < dist[v]))
v = j;
}
if(dist[v] == INT_MAX)
break;
vis[v] = true;
for(int j=0;j<=nodes;j++)
dist[j] = min(dist[j], dist[v]+dp[v][j]);
}
cout<<dist[1];
return 0;
}