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;
const uint64_t seed = std::chrono::system_clock::now().time_since_epoch().count();
mt19937_64 rnd(seed);
const int MOD = 998244353;

#ifdef VIPJML_LOCAL
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << "{";
    for (typename vector<T>::const_iterator vi = v.begin(); vi != v.end(); ++vi)
    {
        if (vi != v.begin())
            os << ", ";
        os << *vi;
    }
    os << "}";
    return os;
}
template <typename A, typename B>
ostream &operator<<(ostream &os, const vector<pair<A, B>> &v)
{
    os << "{";
    for (typename vector<pair<A, B>>::const_iterator vi = v.begin(); vi != v.end(); ++vi)
    {
        if (vi != v.begin())
            os << ", ";
        os << '(' << vi->first << " " << vi->second << ")";
    }
    os << "}";
    return os;
}

template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p)
{
    os << '(' << p.first << ", " << p.second << ')';
    return os;
}

void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T)
{
    cerr << ' ' << H;
    dbg_out(T...);
}
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
using LL = long long;

const int N = 55;
LL dp[N][N][N][5][5];
void solve(int caseNum)
{
    int n, k;
    cin >> n >> k;
    vector<LL> L(n), R(n), C(k + 1, 0);
    for (int i = 0; i < n; i++)
        cin >> L[i] >> R[i];
    for (int i = 0; i < k; i++)
        cin >> C[i];
    vector<int> pos(n, -1), pos1(n, k + 1), pos2(n, k + 1);
    for (int i = 0; i < n; i++)
    {
        for (int j = k - 1; j >= 0; j--)
        {
            if ((L[i] >> j & 1) != (R[i] >> j & 1))
            {
                pos[i] = j;
                break;
            }
        }

        for (int j = 0; j <= k; j++)
        {
            if ((R[i] >> j & 1) == 0)
            {
                pos1[i] = j;
                break;
            }
        }

        for (int j = 0; j <= k; j++)
        {
            if ((L[i] >> j & 1) == 1)
            {
                pos2[i] = j;
                break;
            }
        }
    }
    dbg(pos, pos2, pos1);
    dbg(C);
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++)
            for (int t = 0; t <= k + 1; t++)
                for (int kk = 0; kk < 5; kk++)
                    for (int l = 0; l < 5; l++)
                    {
                        if (t == k + 1 && (kk == 1 || kk == 2) && (l == 1 || l == 2) && (j - i <= 1))
                        {
                            dp[t][i][j][kk][l] = 0;
                        }
                        else
                            dp[t][i][j][kk][l] = LLONG_MAX;
                    }
    auto getV1 = [&](int i, int p1, int a1) {
        if (pos[i] <= a1 && p1 >= 3)
            return false;
        if (pos[i] < a1 && p1 == 0)
            return false;
        if (pos[i] == a1 && p1 == 0)
        {
            if (pos1[i] <= a1 || pos2[i] <= a1)
                return false;
        }

        if (p1 == 3 && (L[i] >> a1 & 1) == 1)
        {
            return false;
        }

        if (p1 == 4 && (R[i] >> a1 & 1) == 0)
            return false;

        return true;
    };

    auto getV2 = [&](int i, int p1, int a1) {
        LL t1 = (L[i] >> a1 & 1);
        LL t2 = (R[i] >> a1 & 1);
        LL r1;
        if (p1 == 1)
            r1 = t1;
        else if (p1 == 2)
            r1 = t2;
        else if (p1 == 3)
            r1 = 1 - t1;
        else
            r1 = 1 - t2;
        //dbg(i, p1, a1, r1);
        return r1;
    };

    auto cacl = [&](int i, int j, int p1, int p2, int a1) {
        if (getV2(i, p1, a1) == getV2(j, p2, a1))
            return 0LL;
        return 1LL * C[a1];
    };
    for (int a1 = k; a1 >= 0; a1--)
    {
        for (int len = 1; len <= n; len++)
        {
            for (int i = 0; i + len <= n; i++)
            {
                for (int p1 = 4; p1 >= 0; p1--)
                    for (int p2 = 4; p2 >= 0; p2--)
                    {

                        if (!(getV1(i, p1, a1) && getV1(i + len - 1, p2, a1)))
                        {
                            continue;
                        }
                        if (len == 1)
                        {
                            if (p1 != p2)
                                continue;
                            if (p1 == 0)
                            {
                                dp[a1][i][i + len - 1][p1][p2] = min(
                                    min(dp[a1 + 1][i][i + len - 1][3][3], dp[a1 + 1][i][i + len - 1][4][4]),
                                    dp[a1 + 1][i][i + len - 1][0][0]);

                                if (pos2[i] > a1)
                                    dp[a1][i][i + len - 1][p1][p2] = min(
                                        dp[a1 + 1][i][i + len - 1][1][1],
                                        dp[a1][i][i + len - 1][p1][p2]);
                                if (pos1[i] > a1)
                                    dp[a1][i][i + len - 1][p1][p2] = min(
                                        dp[a1 + 1][i][i + len - 1][2][2],
                                        dp[a1][i][i + len - 1][p1][p2]);
                            }
                            else
                            {
                                dp[a1][i][i + len - 1][p1][p2] = 0;
                            }
                        }
                        else
                        {
                            for (int j = i + 1; j < i + len - 1; j++)
                            {
                                vector<int> ss = {3, 4};
                                if (a1 == 0)
                                {
                                    ss.push_back(1);
                                    ss.push_back(2);
                                }
                                else
                                {
                                    if (pos[j] > a1 && pos2[j] >= a1)
                                        ss.push_back(1);
                                    if (pos[j] > a1 && pos1[j] >= a1)
                                        ss.push_back(2);
                                }
                                for (int x : ss)
                                    if (dp[a1][i][j][p1][x] != LLONG_MAX && dp[a1][j][i + len - 1][x][p2] != LLONG_MAX)
                                        dp[a1][i][i + len - 1][p1][p2] =
                                            min(dp[a1][i][i + len - 1][p1][p2],
                                                dp[a1][i][j][p1][x] + dp[a1][j][i + len - 1][x][p2]);
                            }
                            vector<int> ppp1;
                            vector<int> ppp2;
                            if (p1 > 0)
                                ppp1 = {p1 > 2 ? p1 - 2 : p1};
                            else
                            {
                                ppp1 = {0, 3, 4};
                                if (pos1[i] > a1)
                                    ppp1.push_back(2);
                                if (pos2[i] > a1)
                                    ppp1.push_back(1);
                            }
                            if (p2 > 0)
                                ppp2 = {p2 > 2 ? p2 - 2 : p2};
                            else
                            {
                                ppp2 = {0, 3, 4};
                                if (pos1[i + len - 1] > a1)
                                    ppp2.push_back(2);
                                if (pos2[i + len - 1] > a1)
                                    ppp2.push_back(1);
                            }
                            int pp1 = p1;
                            int pp2 = p2;
                            if (p1 >= 3)
                                pp1 = p1 - 2;
                            if (p2 >= 3)
                                pp2 = p2 - 2;
                            if (p1 > 0 && p2 > 0)
                            {
                                //dbg(i, i + len - 1, p1, p2, a1, cacl(i, i + len - 1, p1, p2, a1));
                                if (dp[a1 + 1][i][i + len - 1][pp1][pp2] != LLONG_MAX)
                                    dp[a1][i][i + len - 1][p1][p2] =
                                        min(dp[a1][i][i + len - 1][p1][p2],
                                            dp[a1 + 1][i][i + len - 1][pp1][pp2] +
                                                cacl(i, i + len - 1, p1, p2, a1));
                            }
                            else
                            {
                                for (int v1 : ppp1)
                                    for (int v2 : ppp2)
                                    {
                                        dp[a1][i][i + len - 1][p1][p2] =
                                            min(dp[a1][i][i + len - 1][p1][p2],
                                                dp[a1 + 1][i][i + len - 1][v1][v2]);
                                    }
                            }
                        }
                    }
            }
        }
    }
    LL ans = LLONG_MAX;
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
        {
            ans = min(ans, dp[0][0][n - 1][i][j]);
        }
    for (int a1 = k - 1; a1 >= 0; a1--)
    {
        for (int len = 1; len <= n; len++)
        {
            for (int i = 0; i + len <= n; i++)
            {
                for (int p1 = 4; p1 >= 0; p1--)
                    for (int p2 = 4; p2 >= 0; p2--)
                    {
                        // dbg(a1, i, i + len - 1, p1, p2, dp[a1][i][i + len - 1][p1][p2]);
                    }
            }
        }
    }
    cout << ans << endl;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.precision(10);
    int T = 1;
    //cin >> T;
    for (int i = 1; i <= T; i++)
    {
        solve(i);
    }
    cout.flush();
    return 0;
}