#include<bits/stdc++.h>
using namespace std;
template<typename T>inline T read(){
	T f=0,x=0;char c=getchar();
	while(!isdigit(c)) f=c=='-',c=getchar();
	while(isdigit(c)) x=x*10+c-48,c=getchar();
	return f?-x:x;
}
#define int long long
namespace run{
	const int N=69,inf=1e18;
	int n,a[N],K,bound[N][2],c[N],tp[N],f[N][N][N][2][2],g[N][N][2][2][2][2],h[N][2];
	int main(){
		n=read<int>(),K=read<int>();
		for(int i=1;i<=n;i++) bound[i][0]=read<int>(),bound[i][1]=read<int>();
		for(int i=0;i<K;i++) c[i]=read<int>();

		for(int i=1;i<=n;i++){
			tp[i]=-1;
			for(int j=K-1;~j;j--)
				if((bound[i][0]>>j&1)^(bound[i][1]>>j&1)){tp[i]=j;break;}
		}tp[0]=tp[n+1]=-1;

		memset(f,0x3f,sizeof f);
		for(int l=1;l<=n+1;l++) f[K][l][l-1][0][0]=0;
		for(int t=K-1;~t;t--){
		//	cout<<t<<":--------------------------"<<endl;
			memset(g,0x3f,sizeof g);
			for(int l=1;l<=n+1;l++) for(int r=l-1;r<=n;r++)
				for(int p=0;p<2;p++) for(int q=0;q<2;q++){
					int _p=tp[l-1]==t?0:p,_q=tp[r+1]==t?0:q,tmp=0;
					int b1=bound[l-1][p]>>t&1,b2=bound[r+1][q]>>t&1;

					if(l-1>=1 && r+1<=n) tmp=c[t]*(b1^b2);
					g[l][r][p][q][0][0]=f[t+1][l][r][_p][_q]+tmp;
					if(tp[l-1]>t && tp[r+1]>t) g[l][r][p][q][1][1]=f[t+1][l][r][_p][_q]+tmp;
					tmp=0;

					if(l-1>=1 && r+1<=n) tmp=c[t]*(b1^b2^1);
					if(tp[l-1]>t) g[l][r][p][q][1][0]=f[t+1][l][r][_p][_q]+tmp;
					if(tp[r+1]>t) g[l][r][p][q][0][1]=f[t+1][l][r][_p][_q]+tmp;
					tmp=0;
				}
			for(int len=0;len<=n;len++){
				for(int l=1;l+len-1<=n;l++){
					int r=l+len-1;
					for(int p=0;p<2;p++) for(int q=0;q<2;q++) 
						for(int i=l;i<=r;i++)
							for(int h=0;h<2;h++) if(((bound[i][h]>>t)&1)==h)
								for(int b1=0;b1<2;b1++) for(int b2=0;b2<2;b2++)
									g[l][r][p][q][b1][b2]=min(g[l][r][p][q][b1][b2],g[l][i-1][p][h][b1][1]+g[i+1][r][h][q][1][b2]);
				}
			}
			for(int l=1;l<=n+1;l++) for(int r=l-1;r<=n;r++)
				for(int p=0;p<2;p++) for(int q=0;q<2;q++){
					f[t][l][r][p][q]=g[l][r][p][q][0][0];
					//	cout<<l<<" "<<r<<" "<<p<<" "<<q<<":"<<f[t][l][r][p][q]<<endl;
				}
		}

		memset(h,0x3f,sizeof h);
		h[0][0]=0;
		for(int i=1;i<=n+1;i++) for(int j=0;j<i;j++) 
			for(int p=0;p<2;p++) for(int q=0;q<2;q++) 
				h[i][p]=min(h[i][p],h[j][q]+f[0][j+1][i-1][q][p]);
		printf("%lld\n",h[n+1][0]);
		return 0;
	}
}
#undef int
int main(){
#ifdef my
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
#endif
	return run::main();
}