#include<bits/stdc++.h>
typedef long long LL;
const LL maxn=59,inf=1e18;
void Chkmin(LL &x,LL y){
	if(y<x) x=y;
}
LL n,K;
LL lim[maxn][2],hb[maxn],f[maxn][maxn][maxn][4][4],c[maxn];
LL lg(LL x){
	LL len(0);
	while(x) x>>=1,++len;
	return len;
}
bool Check(LL i,LL l,LL r){
	LL flag(1);
	for(LL k=l;k<=r;++k) flag&=(i<(hb[k]-1));
	return flag;
}
int main(){
	scanf("%lld%lld",&n,&K);
	for(LL i=1;i<=n;++i){
		scanf("%lld%lld",&lim[i][0],&lim[i][1]);
		lim[i][0]+=(1ll<<K); lim[i][1]+=(1ll<<K);
		lim[i][0]--; lim[i][1]++;
		hb[i]=lg(lim[i][0]^lim[i][1])-1;
	}
	for(LL i=0;i<K;++i){
		scanf("%lld",c+i);
	}
	lim[0][0]=lim[1][0];
	lim[0][1]=lim[1][1];
	lim[n+1][0]=lim[n][0];
	lim[n+1][1]=lim[n][1];
	hb[0]=hb[1]; hb[n+1]=hb[n];
	K+=2;
	memset(f,63,sizeof(f));
	for(LL l=0;l<=n;++l){
		for(LL bit1=0;bit1<2;++bit1){
			for(LL bit2=0;bit2<2;++bit2){
				f[K][l][l+1][bit1][bit2]=0;
			}
		}
	}
	//for(LL i=0;i<=n+1;++i) printf("%lld ",hb[i]); puts("");
	for(LL i=K-1;i>=0;--i){
		for(LL l=0;l<=n;++l){
			for(LL r=l+1;r<=n+1;++r){
				for(LL bit1=0;bit1<4;++bit1){
					for(LL bit2=0;bit2<4;++bit2){
						if(bit1>>1 && !(i<hb[l] && (lim[l][bit1&1]>>i&1)==(bit1&1))) continue;
						if(bit2>>1 && !(i<hb[r] && (lim[r][bit2&1]>>i&1)==(bit2&1))) continue;
						if(Check(i,l+1,r-1)){
							//printf("(%lld,%lld,%lld)(%lld,%lld)",l,r,i,bit1,bit2);
							LL x(lim[l][bit1&1]>>i&1),y(lim[r][bit2&1]>>i&1);
							if(bit1>>1) x^=1;
							if(bit2>>1) y^=1;
							//printf("%lld\n",x*y*c[i]);
							if(l>=1 && r<=n)
							    Chkmin(f[i][l][r][bit1][bit2],f[i+1][l][r][bit1&1][bit2&1]+(x^y)*c[i]);
							else
								Chkmin(f[i][l][r][bit1][bit2],f[i+1][l][r][bit1&1][bit2&1]);
						}
					}
				}
			}
		}
		for(LL l=0;l<=n;++l){
			for(LL r=l+1;r<=n+1;++r){
				for(LL bit1=0;bit1<4;++bit1){
					for(LL bit2=0;bit2<4;++bit2){
						for(LL mid=l+1;mid<r;++mid){
							Chkmin(f[i][l][r][bit1][bit2],f[i][l][mid][bit1][2]+f[i][mid][r][2][bit2]);
							Chkmin(f[i][l][r][bit1][bit2],f[i][l][mid][bit1][3]+f[i][mid][r][3][bit2]);
						}
					}
				}
			}
		}
	}
	printf("%lld\n",f[0][0][n+1][0][0]);
	return 0;
}