#include<bits/stdc++.h>
using namespace std;
const int N=57; long long opt[N][3][2];
long long n,k,l[N],r[N],c[N],dp[N][N][N][3][3],sum[N][N][3][3]; bool fl[N][N][2],ft[N][N][2];
inline void chkmin(long long &a,long long b){
	if(a==-1) a=b; else a=min(a,b);
}
inline int solve(int a,int b,int c){
	if(c==2) return -1;
	return ft[a][b][c];
}
inline int solvex(int a,int b,int c){
	if(c==2) return -1; return (c^1);
}
inline int getans(int a,int b){
	if(a==-1||b==-1) return 0; return (a^b);
}
int main(){
	cin>>n>>k; long long A=0;
	for(int i=1;i<=n;i++) cin>>l[i]>>r[i];
	for(int i=0;i<k;i++) cin>>c[i],A+=(n-1)*c[i];
	for(int i=1;i<=n;i++)
		for(int j=1;j<k;j++)
			if((l[i]>>(j+1))!=(r[i]>>(j+1))){
				if(!(l[i]&(1ll<<j))) fl[i][j][0]=1;
				if((r[i]&(1ll<<j))) fl[i][j][1]=1;
			}
	for(int i=1;i<=n;i++){
		for(int j=0;j<k;j++){
			if(((1ll<<j)&l[i])) ft[i][j][0]=1;
			if(((1ll<<j)&r[i])) ft[i][j][1]=1;
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
			for(int t=0;t<k;t++)
				for(int a=0;a<=2;a++)
					for(int b=0;b<=2;b++) dp[i][j][t][a][b]=A;
	for(int t=k-1;t>=1;t--){
		memset(sum,-1,sizeof(sum)); long long S=c[t];
		for(int i=1;i<=n;i++){
			for(int a=0;a<=2;a++) sum[i][i-1][a][a]=0;
			for(int j=i;j<=n;j++){
				if(fl[j][t][0]){
					for(int k=i-1;k<j;k++)
						for(int a=0;a<=2;a++)
							for(int b=0;b<=2;b++)
								if(sum[i][k][a][b]!=-1){
									int A=1,B=solvex(k,t,b); if(k==i-1) B=solve(k,t,b);
									chkmin(sum[i][j][a][0],sum[i][k][a][b]+dp[k+1][j-1][t][b][0]+getans(A,B)*S);
								}
				}
				if(fl[j][t][1]){
					for(int k=i-1;k<j;k++)
						for(int a=0;a<=2;a++)
							for(int b=0;b<=2;b++)
								if(sum[i][k][a][b]!=-1){
									int A=0,B=solvex(k,t,b); if(k==i-1) B=solve(k,t,b);
									chkmin(sum[i][j][a][1],sum[i][k][a][b]+dp[k+1][j-1][t][b][1]+getans(A,B)*S);
								}
				}
			}
			for(int j=i;j<=n;j++)
				for(int k=i-1;k<=j;k++)
					for(int a=0;a<=2;a++)
						for(int b=0;b<=2;b++)
							for(int c=0;c<=2;c++)
								if(sum[i][k][a][b]!=-1){
									int A=solvex(k,t,b),B=solve(j+1,t,c); if(k==i-1) A=solve(k,t,b);
									chkmin(dp[i][j][t-1][a][c],sum[i][k][a][b]+getans(A,B)*S+dp[k+1][j][t][b][c]);
								}
		}
		for(int i=1;i<n;i++)
			for(int a=0;a<=2;a++)
				for(int b=0;b<=2;b++)
					dp[i+1][i][t-1][a][b]=dp[i+1][i][t][a][b]+getans(solve(i,t,a),solve(i+1,t,b))*S;
	}
	long long S=c[0];
	memset(opt,-1,sizeof(opt)),opt[0][2][0]=0; long long ans=A;
	for(int i=0;i<=n;i++)
		for(int j=i+1;j<=n+1;j++)
			for(int a=0;a<=2;a++)
				for(int b=0;b<=1;b++){
					if(opt[i][a][b]==-1) continue;
					ans=min(ans,opt[i][a][b]+dp[i+1][n][0][a][2]);
					long long S=(c[0]*(a!=2));
					chkmin(opt[j][0][solve(j,0,0)],opt[i][a][b]+getans(b,solve(j,0,0))*S+dp[i+1][j-1][0][a][0]);
					if((!(l[j]&1))&&l[j]+1<=r[j]){
						chkmin(opt[j][0][solve(j,0,0)^1],opt[i][a][b]+getans(b,solve(j,0,0)^1)*S+dp[i+1][j-1][0][a][0]);
					}
					chkmin(opt[j][1][solve(j,0,1)],opt[i][a][b]+getans(b,solve(j,0,1))*S+dp[i+1][j-1][0][a][1]);
					if((r[j]&1)&&l[j]+1<=r[j]){
						chkmin(opt[j][1][solve(j,0,1)^1],opt[i][a][b]+getans(b,solve(j,0,1)^1)*S+dp[i+1][j-1][0][a][1]);
					}
				}
	cout<<ans<<endl;
}