神仙题。不愧是 3500 。

我们考虑对于每个数，它必然有一个脱离限制的位。也就是说，每个位置实际上放的值，必然是和 $L$ 或者 $R$ 存在一段 $\text{LCP}$ ，然后下一位脱离限制，然后后面的随意填。

于是我们考虑一个贪心，如果我们知道了 $1 \sim n$ 的所有数中脱离限制位最低的是谁，那么这个脱离限制位之下的所有位对于所有数都是可以随便放的，所以我们一定全放 $0$ 或者全放 $1$ 最优。

我们可以把这个问题推广到任何一个区间上。对于一段区间 $l,r$ ，我们可以枚举脱离限制最低位是谁，再枚举它脱离限制的位，那么我们可以在这下面的位随意发挥。那么如果 $l-1,r+1$ 在下面某一位不同，就必须得在这位有 $1$ 的贡献，否则可以没有贡献。

但是注意到 $l-1,r+1$ 这两个数并不好存下来，因为值域太大。但是我们可以钦定这两个数在当前考虑的位已经被限制上了，于是可以用两个 $0/1$ 表示这个数前面的位贴紧 $l$ 还是 $r$ 以及最下面的位是否被翻转。

于是可以设置出状态 $dp[c][l][r][0/1][0/1][0/1][0/1]$ 表示当前只考虑 $\ge c$ 的位，下面的位不管，区间为 $l,r$ 而 $l-1,r+1$ 的状态分别由两个 $0/1$ 表示。转移分为两种，一种是区间内不存在正好 $c$ 位脱离限制的，那么直接由 $dp[c+1][l][r][0/1][0/1][0/1][0/1]$ 转移过来，再加上这一位的贡献，由左右在这一位是否不同决定。还有一种是枚举一下在 $k$ 脱离限制，就由 $dp[c][l][k-1][…]$ 和 $dp[c][k+1][r][…]$ 转移过来。而如果 $l > r$ 则意味着所有里面的位置都被钦定过了，显然只能走第一种转移。如果 $c = k$ 那么只有在 $l > r$ 的时候才有值，因为到最后一定必须确定所有数。

于是就做完了，写记搜会好写得多。

复杂度 $O(n^3k)$ 带一个大常数，跑着还是很快的。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 56
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , k;
ll L[MAXN] , R[MAXN] , C[MAXN];
ll dp[MAXN][MAXN][MAXN][2][2][2][2];

inline void ckm( ll& a , ll b ) {
	a = min( a , b );
}
ll wkr( int c , int l , int r , int l1 , int l2 , int r1 , int r2 ) {
	if( c == k ) return l > r ? 0 : 1e18;
	ll& s = dp[c][l][r][l1][l2][r1][r2];
	if( ~s ) return s;
	ll lt = ( ( l1 ? R[l - 1] : L[l - 1] ) >> c ) ^ l2;
	ll rt = ( ( r1 ? R[r + 1] : L[r + 1] ) >> c ) ^ r2;
	s = 1e18;
	ckm( s , wkr( c + 1 , l , r , l1 , 0 , r1 , 0 ) + ( l != 1 && r != n ? ( ( lt & 1 ) ^ ( rt & 1 ) ) * C[c] : 0 ) );
	rep( k , l , r ) rep( t , 0 , 1 ) {
		if( !c ) ckm( s , wkr( c , l , k - 1 , l1 , l2 , t , 0 ) + wkr( c , k + 1 , r , t , 0 , r1 , r2 ) );
		ll w = ( t ? R[k] : L[k] );
		if( L[k] <= ( ( w ^ ( 1ll << c ) ) & ( ~( ( 1ll << c ) - 1 ) ) ) && ( ( w ^ ( 1ll << c ) ) | ( ( 1ll << c ) - 1 ) ) <= R[k] ) 
			ckm( s , wkr( c , l , k - 1 , l1 , l2 , t , 1 ) + wkr( c , k + 1 , r , t , 1 , r1 , r2 ) );
	}
	return s;
}

void solve() {
	cin >> n >> k;
	rep( i , 1 , n ) scanf("%lld%lld",L + i,R + i);
	rep( i , 0 , k - 1 ) scanf("%lld",C + i);
	memset( dp , -1 , sizeof dp );
	cout << wkr( 0 , 1 , n , 0 , 0 , 0 , 0 ) << endl;
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}