考虑一个 \(L\le x\le R\) 的数 \(x\)，必然是一段前缀贴着 \(L\) 或者 \(R\)，然后下一位脱离了 \(L\) 和 \(R\) 的限制，后面随便乱填。
注意到一个性质，对于某一位 \(d\)，考虑这一位上没有限制的那些位置，最优方案肯定是令其等于其左边（或者右边）第一个有限制的数的第 \(d\) 位上的值。这样对于每一位，我们只用考虑它有限制的那些位，计算相邻不同的数量。
这不难让我们想到区间 DP 的模型：\(dp_{x,l,r,0/1,0/1,0/1,0/1}\) 表示现在填好了 \(x\) 以下的位，当前区间为 \([l,r]\)，\(l-1\) 是贴紧下界还是上界，\(l-1\) 最下面的位是否被翻转，\(r+1\) 是贴紧下界还是上界，\(r+1\) 最下面的位是否被翻转。考虑转移，如果没有恰好在 \(2^x\) 位脱离限制的位置，那就直接从 \(dp_{x+1,l,r}\) 转移过来，否则我们枚举这个位置 \(k\) 然后从 \(dp_{x,l,k-1}+dp_{x,k+1,r}\) 转移即可。
使用记忆化搜索实现很方便。时间复杂度 \(n^4\)。
const int MAXN=50;
const ll INF=1e18;
int n,k;ll L[MAXN+5],R[MAXN+5],c[MAXN+5],dp[MAXN+5][MAXN+5][MAXN+5][2][2][2][2];
ll calc(int x,int l,int r,int l1,int l2,int r1,int r2){
if(x==k)return (l>r)?0:INF;
if(~dp[x][l][r][l1][l2][r1][r2])return dp[x][l][r][l1][l2][r1][r2];
int lb=(((l1)?R[l-1]:L[l-1])>>x&1)^l2;
int rb=(((r1)?R[r+1]:L[r+1])>>x&1)^r2;
ll &ret=dp[x][l][r][l1][l2][r1][r2];
ret=calc(x+1,l,r,l1,0,r1,0)+((l!=1&&r!=n&&lb!=rb)?c[x]:0);
for(int k=l;k<=r;k++)for(int t=0;t<2;t++){
if(!x)chkmin(ret,calc(x,l,k-1,l1,l2,t,0)+calc(x,k+1,r,t,0,r1,r2));
ll w=t?R[k]:L[k],_l=(w^(1ll<<x))&(~((1ll<<x)-1)),_r=(w^(1ll<<x))|((1ll<<x)-1);
if(L[k]<=_l&&_r<=R[k])chkmin(ret,calc(x,l,k-1,l1,l2,t,1)+calc(x,k+1,r,t,1,r1,r2));
}return ret;
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)scanf("%lld%lld",&L[i],&R[i]);
for(int i=0;i<k;i++)scanf("%lld",&c[i]);
memset(dp,-1,sizeof(dp));printf("%lld\n",calc(0,1,n,0,0,0,0));
return 0;
}