Problem: Given integers c_{0}, c_{1}, …, c_{k-1} we can define the cost of a number 0 ≤ x < 2^{k} as p(x) = ∑_{i=0}^{k-1} \left( \left⌊ \frac{x}{2^{i}} \right⌋ mod 2 \right) ⋅ c_{i}. In other words, the cost of number x is the sum of c_{i} over the bits of x which are equal to one.

Let's define the cost of array a of length n ≥ 2 with elements from [0, 2^{k}) as follows: cost(a) = ∑_{i=1}^{n - 1} p(a_{i} ⊕ a_{i+1}), where ⊕ denotes [bitwise exclusive OR](https://en.wikipedia.org/wiki/Exclusive_or) operation.

You have to construct an array of length n with minimal cost, given that each element should belong to the given segment: l_{i} ≤ a_{i} ≤ r_{i}.

Input

The first line contains two integers n and k (2 ≤ n ≤ 50, 1 ≤ k ≤ 50) — the size of an array and bit length of the numbers in question.

Next n lines contain the restrictions for elements of the array: the i-th line contains two integers l_{i} and r_{i} (0 ≤ l_{i} ≤ r_{i} < 2^{k}).

The last line contains integers c_{0}, c_{1}, …, c_{k-1} (0 ≤ c_{i} ≤ 10^{12}).

Output

Output one integer — the minimal cost of an array satisfying all the restrictions.

Examples

Input


4 3
3 3
5 5
6 6
1 1
5 2 7


Output


30


Input


3 3
2 2
3 4
4 6
1 10 100


Output


102

Note

In the first example there is only one array satisfying all the restrictions — [3, 5, 6, 1] — and its cost is equal to cost([3, 5, 6, 1]) = p(3 ⊕ 5) + p(5 ⊕ 6) + p(6 ⊕ 1) = p(6) + p(3) + p(7) = (c_{1} + c_{2}) + (c_{0} + c_{1}) + (c_{0} + c_{1} + c_{2}) = (2 + 7) + (5 + 2) + (5 + 2 + 7) = 30.

In the second example the only optimal array is [2, 3, 6].

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define LL long long
#define ld long double
#define For(i,x,y)	for(ll i=(x);i<=(y);++i)
#define FOr(i,x,y)	for(ll i=(x);i>=(y);--i)
#define rep(i,x,y)	for(ll i=(x);i<(y);++i)
#define clr(a,v)	memset(a,v,sizeof(a))
#define cpy(a,b)	memcpy(a,b,sizeof(a))
#define fi	first 
#define se	second
#define	pb	push_back
#define mk	make_pair
#define pa	pair<ll,ll>
#define y1	y11111111111111
#define debug	puts("@@@@@@@@@@@@@@@@@@@@@@@")
const double eps = 1e-7;
ll read(){
	ll x=0,f=1;	char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())	if (ch=='-')	f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())	x=x*10+ch-'0';
	return x*f;
}
void write(ll x){
	if (x<0)	putchar('-'),write(-x);
	else{
		if (x>=10)	write(x/10);
		putchar(x%10+'0');
	}
}

const LL MAXN = 55;
LL n,k;
LL bd[MAXN][2];
LL c[MAXN],keybit[MAXN];
LL dp[MAXN][MAXN][MAXN][2][2][2][2];
inline bool judge(int l,int r,int i)
{
	for (int mid = l+1; mid <= r-1; ++mid)
		if (i >= keybit[mid]-1) return 0;
	return 1;
}
int main()
{
	n=read();k=read();
	For(i,1,n)bd[i][0]=read()-1+(1ll<<k),bd[i][1]=read()+1+(1ll<<k);
	For(i,0,k-1)c[i]=read();
	
	For(i,1,n)
	{
		for (int j = k+3; j >= 0; --j)
		if ((bd[i][0]>>j)^(bd[i][1]>>j)) 
			{keybit[i] = j; break;}
	}k+=2;
	bd[0][0] = bd[1][0]; bd[0][1] = bd[1][1]; keybit[0] = keybit[1];
	bd[n+1][0] = bd[n][0]; bd[n+1][1] = bd[n][1]; keybit[n+1] = keybit[n];
//	for (int i = 0; i <= n+1; ++i) cerr<<keybit[i]<<' ';
	memset(dp,63,sizeof(dp));
	For(l,0,n)
	For(r,l+1,n+1)
	{
		For(lk,0,1) For(lc,0,1) For(rk,0,1) For(rc,0,1)
		dp[k][l][r][lk][lc][rk][rc] = 0;
	}
	FOr(i,k,0)
		For(len,1,n+1)
			For(l,0,n)
			{
				int r=l+len;
				if (r>n+1) continue;	
				For(lk,0,1)For(lc,0,1)For(rk,0,1)For(rc,0,1)
				{
					LL res = dp[i][l][r][lk][lc][rk][rc];
					if(lc&&!(i<keybit[l]&&(bd[l][lk]>>i&1)==lk)) continue;
					if(rc&&!(i<keybit[r]&&(bd[r][rk]>>i&1)==rk)) continue;
					//如果当前位低于keybit位且取值keybit位是一样的，那么这一位必须取的和bd一样，不可以选择作为锁定位 
					if (judge(l,r,i))
						res = min(res,dp[i+1][l][r][lk][0][rk][0]+(1<=l&&r<=n)*(((bd[l][lk]>>i&1)^lc)^((bd[r][rk]>>i&1)^rc))*c[i]);
					For(mid,l+1,r-1)
					{
						res = min(res,dp[i][l][mid][lk][lc][1][1]+dp[i][mid][r][1][1][rk][rc]);
						res = min(res,dp[i][l][mid][lk][lc][0][1]+dp[i][mid][r][0][1][rk][rc]);
					}
					dp[i][l][r][lk][lc][rk][rc] = res;
				//	cout<<i<<' '<<l<<' '<<r<<' '<<lk<<' '<<lc<<' '<<rk<<' '<<rc<<' '<<res<<endl;
				}
			}
	ll ans = (ll)1e18;
	For(lk,0,1)For(lc,0,1)For(rk,0,1)For(rc,0,1)
		ans = min(ans,dp[0][0][n+1][lk][lc][rk][rc]);
	printf("%lld\n",ans);
}
/*
idea:
1）带lb,rb的数位DP基础思想部分
我们可以把lb,rb的最低不同的数字位记为keybit位
则我们可以这样划分出一个个数段：
①在keybit位枚举这一位取0还是取1，这将决定接下来只需考虑lb还是rb
②如果取了0，那么对于lb在keybit以下的每个1位我们必须照搬，每个0位则可以考虑照搬或者置1并使得下面的位可以任意取。
反之，rb的0位需要照搬，1位则有两种决策
所有这些决策加在一起构成lb到rb的所有数段。
我们称被锁定的位为locked位，未被锁定的为free的，特别的把最低locked位记为minlock。注意minlock是可以从第0位到第keybit位枚举的而不是一个定值 
2） 我们考虑剥离区间。如果一个区间(l,r)满足a[l]和a[r]的第i位locked，但a[l+1]到a[r-1]的第i位是free的，那么如果a[l]^a[r]=1,答案贡献c[i].
(中间的free可以全部取a[l]>>i或者a[r]>>i)
结合（1）（2） 我们考虑dp,
dp(i,l,r,lk(01),lc(01),rk(01),rc(01))表示：含于区间(l,r)的所有剥离区间在高于等于i位上的贡献
其中：lk表示a[l]的keybit的取值，lc表示a[l]的minlock位是否等于第i位。（等于是1，小于是0） 
考虑确定所有lock位的情况：可以发现第keybit位是由我们钦定的，第minlock位和第keybit位必然相反，其他都和lb/rb的位相同
换句话说就是如果keybit=1,那么高于minlock位上除了minlock位是相异的之外都和rb相同，反之都和lb相同 
为了方便不妨把lb[l]和lb[r]记成bd[l][0]和bd[l][1]
于是得到两种转移：
转移一：算掉这一位的贡献并且考虑更高位。那么lc和rc必然要置0， ret = max(ret,dp(i+1,l,r,lk,0,rk,0)+(((bd[l][lk]>>i&1)^(lc)^((bd[r][rk]>>i&1 ^ (rc))*c[i]);
转移二：拆分区间。我们要从l+1到r-1里面取一个位置mid使得其在第i位上是lock的，这个mid的keybit需要确定一下，而minlock位需要从i开始 
 那么ret = max(ret, max(dp(i,l,mid,lk,lc,0,1)+dp(i,mid,r,0,1,rk,rc),dp(i,l,mid,lk,lc,1,1)+dp(i,mid,r,1,1,rk,rc)) 
 


*/