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:
//#define DEBUG
//#define USEPB_DS
#define USETR1
#define CPPELEVEN
#define GPP

/*
 * temp.cpp
 *
 *  Created on: 2012-7-18
 *      Author: BSBandme
 */
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#if __cplusplus < 201500L
#include <bits/stdc++.h>
#else
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <cassert>
#include <list>
#include <iomanip>
#include <cmath>
#include <deque>
#include <utility>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <climits>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <functional>
#include <sstream>
#include <tuple>
#endif

using namespace std;

#ifndef CPPELEVEN
#ifdef USETR1
#include <tr1/unordered_map>
#include <tr1/unordered_set>
using namespace tr1;
#endif
#else
#include <unordered_map>
#include <unordered_set>
#endif

#ifdef USEPB_DS
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
// binomial_heap_tag, rc_binomial_heap_tag, thin_heap_tag, binary_heap_tag
typedef __gnu_pbds::priority_queue<int, greater<int>, pairing_heap_tag> pq_type;
// splay_tree_tag, ov_tree_tag
typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> tree_type;
#endif

#define mpr make_pair
typedef unsigned int ui;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<string> vs;
typedef map<string, int> mpsi;
typedef map<double, int> mpdi;
typedef map<int, int> mpii;

const double pi = acos(0.0) * 2.0;
const long double eps = 1e-10;
const int step[8][2] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 1 }, {
		1, 1 }, { 1, -1 }, { -1, -1 } };

template<class T> inline T abs1(T a) {
	return a < 0 ? -a : a;
}

#ifndef CPPELEVEN
template <class T> inline T max1(T a, T b) { return b < a ? a : b; }
template <class T> inline T max1(T a, T b, T c) { return max1(max1(a, b), c); }
template <class T> inline T max1(T a, T b, T c, T d) { return max1(max1(a, b, c), d); }
template <class T> inline T max1(T a, T b, T c, T d, T e) { return max1(max1(a, b, c, d), e); }
template <class T> inline T min1(T a, T b) { return a < b ? a : b; }
template <class T> inline T min1(T a, T b, T c) { return min1(min1(a, b), c); }
template <class T> inline T min1(T a, T b, T c, T d) { return min1(min1(a, b, c), d); }
template <class T> inline T min1(T a, T b, T c, T d, T e) { return min1(min1(a, b, c, d), e); }
#else
template<typename t, typename t1>
t min1(t a, t1 b) {
	return a < b ? a : b;
}
template<typename t, typename ... arg>
t min1(t a, arg ... arr) {
	return min1(a, min1(arr...));
}
template<typename t, typename t1>
t max1(t a, t1 b) {
	return a > b ? a : b;
}
template<typename t, typename ... arg>
t max1(t a, arg ... arr) {
	return max1(a, max1(arr...));
}
#endif

inline int jud(double a, double b) {
	if (abs(a) < eps && abs(b) < eps)
		return 0;
	else if (abs1(a - b) / max(abs1(a), abs1(b)) < eps) return 0;
	if (a < b) return -1;
	return 1;
}
template<typename t> inline int jud(t a, t b) {
	if (a < b) return -1;
	if (a == b) return 0;
	return 1;
}

// f_lb == 1代表返回相同的一串的左边界，f_small == 1代表返回如果没有寻找的值返回小的数
template<typename it, typename t1>
inline int RangeFind(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
	if (na == 0) return 0;
	int be = 0, en = na - 1;
	if (*a <= *(a + na - 1)) {
		if (f_lb == 0)
			while (be < en) {
				int mid = (be + en + 1) / 2;
				if (jud(*(a + mid), val) != 1)
					be = mid;
				else
					en = mid - 1;
			}
		else
			while (be < en) {
				int mid = (be + en) / 2;
				if (jud(*(a + mid), val) != -1)
					en = mid;
				else
					be = mid + 1;
			}
		if (f_small && jud(*(a + be), val) == 1) be--;
		if (!f_small && jud(*(a + be), val) == -1) be++;
	} else {
		if (f_lb)
			while (be < en) {
				int mid = (be + en + 1) / 2;
				if (jud(*(a + mid), val) != -1)
					be = mid;
				else
					en = mid - 1;
			}
		else
			while (be < en) {
				int mid = (be + en) / 2;
				if (jud(*(a + mid), val) != 1)
					en = mid;
				else
					be = mid + 1;
			}
		if (!f_small && jud(*(a + be), val) == -1) be--;
		if (f_small && jud(*(a + be), val) == 1) be++;
	}
	return be;
}

template<class T> inline T lowb(T num) {
	return num & (-num);
}
#ifdef GPP
inline int bitnum(ui nValue) {
	return __builtin_popcount(nValue);
}
inline int bitnum(int nValue) {
	return __builtin_popcount(nValue);
}
inline int bitnum(ull nValue) {
	return __builtin_popcountll(nValue);
}
inline int bitnum(ll nValue) {
	return __builtin_popcountll(nValue);
}
inline int bitmaxl(ui a) {
	if (a == 0) return 0;
	return 32 - __builtin_clz(a);
}
inline int bitmaxl(int a) {
	if (a == 0) return 0;
	return 32 - __builtin_clz(a);
}
inline int bitmaxl(ull a) {
	if (a == 0) return 0;
	return 64 - __builtin_clzll(a);
}
inline int bitmaxl(ll a) {
	if (a == 0) return 0;
	return 64 - __builtin_clzll(a);
}
#else
#endif

long long pow(long long n, long long m, long long mod = 0) {
	if (m < 0) return 0;
	long long ans = 1;
	long long k = n;
	while (m) {
		if (m & 1) {
			ans *= k;
			if (mod) ans %= mod;
		}
		k *= k;
		if (mod) k %= mod;
		m >>= 1;
	}
	return ans;
}

#define  MOD 1000000007
template<class t1, class t2>
inline void add(t1 &a, t2 b, int mod = -1) {
	if (mod == -1) mod = MOD;
	a += b;
	while (a >= mod)
		a -= mod;
	while (a < 0)
		a += mod;
}
template<class t>
void output1(t arr) {
	for (int i = 0; i < (int) arr.size(); i++)
		cerr << arr[i] << ' ';
	cerr << endl;
}
template<class t>
void output2(t arr) {
	for (int i = 0; i < (int) arr.size(); i++)
		output1(arr[i]);
}

//....................密..........封..........线..........下..........禁..........止..........hack...............................................

const int maxn = 55;
ll range[maxn][2];
int n, max_bit;
ll cost[maxn];
ll can[maxn][2][maxn];
ll dp[maxn][maxn][maxn][2][2], dp1[maxn][maxn][maxn][2][2];

ll GetCost(int deep, int i, int j, int cate1, int cate2, int new_stack = false) {
	if (j - i == 1) {
		if (i == 0 || j == n + 1) return 0;
		ll ans = 0;
		for (int bit = max_bit - 1; bit > max(deep - 1, 0); bit--) {
			if ((range[i][cate1] & (1ll << bit)) !=
					(range[j][cate2] & (1ll << bit))) {
				ans += cost[bit];
			}
		}
		if (deep - 1 >= 0) {
			if (new_stack) {
				if (bool(range[i][cate1] & (1ll << (deep - 1))) != 1 - cate2) {
					ans += cost[(deep - 1)];
				}
			} else {
				if ((range[i][cate1] & (1ll << (deep - 1))) !=
						(range[j][cate2] & (1ll << (deep - 1)))) {
					ans += cost[(deep - 1)];
				}
			}
		}
		return ans;
	}
	return new_stack ? dp1[deep][i][j][cate1][cate2] :  dp[deep][i][j][cate1][cate2];
}

ll GetNewCost(int deep, int i, int cate, int newbit) {
	if (i == 0 || i == n + 1 || deep <= 0) return 0;
	return (bool(range[i][cate] & (1ll << (deep - 1))) ^ newbit) * cost[deep - 1];
}

ll ans = 1ll << 60;
ll arr[maxn];
void Dfs(int deep) {
	if (deep == n + 1) {
		ll rans = 0;
		for (int i = 1; i < n; i++) {
			ll rnum = arr[i] ^ arr[i + 1];
			for (int bit = 0; bit < max_bit; bit++) if (rnum & (1ll << bit)) {
				rans += cost[bit];
			}
		}
		if (rans < ans) {
			for (int i = 1; i < deep; i++) cerr << arr[i] << ' ';
			cerr << rans << endl;
			ans = rans;
		}
		return;
	}
	for (int i = range[deep][0]; i <= range[deep][1]; i++) {
		arr[deep] = i;
		Dfs(deep + 1);
	}
}

int main() {

//............................不要再忘了检查maxn大小了！！！！BSBandme你个SB！！！！...................................................

	ios_base::sync_with_stdio(0);
#ifdef DEBUG //......................................................................................................
	freopen("input.txt", "r", stdin);
#endif //...........................................................................................................

	scanf("%d%d", &n, &max_bit);
	for (int i = 1; i <= n; i++) {
		scanf("%I64d%I64d", &range[i][0], &range[i][1]);
		int common = max_bit;
		while (common >= 0 && (range[i][0] & (1ll << common)) ==
				(range[i][1] & (1ll << common))) {
			common--;
		}
		for (int j = common - 1; j >= 0; j--) if (!(range[i][0] & (1ll << j))) {
			can[i][0][j + 1] = 1;
		}
		for (int j = common - 1; j >= 0; j--) if (range[i][1] & (1ll << j)) {
			can[i][1][j + 1] = 1;
		}
		can[i][0][0] = can[i][1][0] = 1;
	}
	for (int i = 0; i < max_bit; i++) scanf("%I64d", cost + i);

	memset(dp, 0x3f, sizeof(dp));
	memset(dp1, 0x3f, sizeof(dp));
	for (int deep = max_bit; deep >= 0; deep--) {
		for (int i = 0; i <= n - 1; i++) for (int j = i + 2; j <= n + 1; j++) {
			for (int cate1 = 0; cate1 < 2; cate1++) for (int cate2 = 0; cate2 < 2; cate2++) {
				for (int mid = i + 1; mid < j; mid++) {
//					if (deep == 1 && i == 4 && j == 6 && cate1 == 0 && cate2 == 0) {
//						cerr << 1 << endl;
//					}
					if (can[mid][0][deep]) {
						dp[deep][i][j][cate1][cate2] = min(
								dp[deep][i][j][cate1][cate2],
								GetCost(deep, i, mid, cate1, 0, true) + GetCost(deep + 1, mid, j, 0, cate2) +
										GetNewCost(deep, j, cate2, 1));
						if (can[j][cate2][deep]) {
							dp1[deep][i][j][cate1][cate2] = min(
									dp1[deep][i][j][cate1][cate2],
									GetCost(deep, i, mid, cate1, 0, true) + GetCost(deep + 1, mid, j, 0, cate2) +
										 (j == n + 1 ? 0 : ((1 - cate2) ^ 1) * cost[deep - 1]));
						}
					}
					if (can[mid][1][deep]) {
						dp[deep][i][j][cate1][cate2] = min(
								dp[deep][i][j][cate1][cate2],
								GetCost(deep, i, mid, cate1, 1, true) + GetCost(deep + 1, mid, j, 1, cate2) +
								    GetNewCost(deep, j, cate2, 0));
						if (can[j][cate2][deep]) {
							dp1[deep][i][j][cate1][cate2] = min(
									dp1[deep][i][j][cate1][cate2],
									GetCost(deep, i, mid, cate1, 1, true) + GetCost(deep + 1, mid, j, 1, cate2) +
									 (j == n + 1 ? 0 : (1 - cate2) * cost[deep - 1]));
						}
					}
				}
				dp[deep][i][j][cate1][cate2] = min(
						dp[deep][i][j][cate1][cate2], dp[deep + 1][i][j][cate1][cate2] + (j == n + 1 ? 0 : GetNewCost(
								deep, i, cate1, bool(range[j][cate2] & (1ll << (deep - 1))))));
				if (can[j][cate2][deep]) {
					dp1[deep][i][j][cate1][cate2] = min(
							dp1[deep][i][j][cate1][cate2], dp[deep + 1][i][j][cate1][cate2] + (j == n + 1 ? 0 : GetNewCost(
									deep, i, cate1, 1 - cate2)));
				}
//				if (dp[deep][i][j][cate1][cate2] < 1ll << 60)
//					cerr << deep << ' ' << i << ' ' << j << ' ' << cate1 << ' ' << cate2 << ' ' <<  dp[deep][i][j][cate1][cate2] << endl;
			}
		}
	}

	printf("%I64d\n", dp[0][0][n + 1][0][0]);

//	Dfs(0);


	return 0;
}