#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using grid = vector<vector<char>>;
//constexpr ll MOD = 1000000007;
constexpr ll MOD = 998244353;
constexpr ll INF = 1050000000;
constexpr ll LONGINF = 1050000000000000000;
struct all_init {
    all_init() {
        cout.tie(nullptr);
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(11);
    };
} ALL_INIT;
struct edge {
 
    int from, to;
    ll cost;
    ll capa;
 
    edge(int s, int d) : from(s), to(d) {
        cost = 0;
        capa = 0;
    }
    edge(int s, int d, ll w) : from(s), to(d), cost(w) { capa = 0; }
    edge(int s, int d, ll x, ll y) : from(s), to(d), cost(x), capa(y) {}
 
    bool operator<(const edge& x) const { return cost < x.cost; }
};
using graph = vector<vector<edge>>;
 
#define CIN(vector_array_etc, n)         \
  for (int loop = 0; loop < n; loop++) { \
    cin >> vector_array_etc[loop];       \
  }
#define COUT(vector_array_etc, n)                                   \
  for (int LOOP = 0; LOOP < n; LOOP++) {                            \
    cout << vector_array_etc[LOOP] << (LOOP == n - 1 ? '\n' : ' '); \
  }
#define VC(Type_name) vector<Type_name>
#define SORT(vector_etc) sort(vector_etc.begin(), vector_etc.end())
#define ALL(vec_etc) vec_etc.begin(), vec_etc.end()
#define VCVC(Type_name) vector<vector<Type_name>>  
#define WARSHALL vector<vector<ll>> g(n, vector<ll>(n, LONGINF))
#define endl '\n'

 
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template <typename T>
istream& operator>>(istream& is, vector<T>& Vec) {
    for (T& x : Vec) {
        is >> x;
    }
    return is;
}
template <typename V, typename H>
void resize(vector<V>& vec, const H head) {
    vec.resize(head);
}
template <typename V, typename H, typename... T>
void resize(vector<V>& vec, const H& head, const T... tail) {
    vec.resize(head);
    for (auto& v : vec) {
        resize(v, tail...);
    }
}
template <ll mod>
struct ModInt {
    long long val;
    constexpr ModInt(long long v = 0) noexcept : val(v% mod) {
        if (val < 0) val += mod;
    }
    constexpr int getmod() { return mod; }
    constexpr ModInt operator-() const noexcept { return val ? mod - val : 0; }
    constexpr ModInt operator+(const ModInt& r) const noexcept {
        return ModInt(*this) += r;
    }
    constexpr ModInt operator-(const ModInt& r) const noexcept {
        return ModInt(*this) -= r;
    }
    constexpr ModInt operator*(const ModInt& r) const noexcept {
        return ModInt(*this) *= r;
    }
    constexpr ModInt operator/(const ModInt& r) const noexcept {
        return ModInt(*this) /= r;
    }
    constexpr ModInt& operator+=(const ModInt& r) noexcept {
        val += r.val;
        if (val >= mod) val -= mod;
        return *this;
    }
    constexpr ModInt& operator-=(const ModInt& r) noexcept {
        val -= r.val;
        if (val < 0) val += mod;
        return *this;
    }
    constexpr ModInt& operator*=(const ModInt& r) noexcept {
        val = val * r.val % mod;
        return *this;
    }
    constexpr ModInt& operator/=(const ModInt& r) noexcept {
        long long a = r.val, b = mod, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b;
            swap(a, b);
            u -= t * v;
            swap(u, v);
        }
        val = val * u % mod;
        if (val < 0) val += mod;
        return *this;
    }
    constexpr bool operator==(const ModInt& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator!=(const ModInt& r) const noexcept {
        return this->val != r.val;
    }
    friend ostream& operator<<(ostream& os, const ModInt<mod>& x) noexcept {
        return os << x.val;
    }
    friend istream& operator>>(istream& is, ModInt<mod>& x) noexcept {
        return is >> x.val;
    }
    friend constexpr ModInt<mod> modpow(const ModInt<mod>& a,
        long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};
template <class T>
struct nCk {
    vector<T> fact_, inv_, finv_;
    constexpr nCk() {}
    constexpr nCk(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) {
        init(n);
    }
    constexpr void init(int n) noexcept {
        fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);
        ll MOD = 1000000007;
        for (ll i = 2; i < n; i++) {
            fact_[i] = fact_[i - 1] * i;
            inv_[i] = -inv_[MOD % i] * (MOD / i);
            finv_[i] = finv_[i - 1] * inv_[i];
        }
    }
    constexpr T com(ll n, ll k) const noexcept {
        if (n < k || n < 0 || k < 0) return 0;
        return fact_[n] * finv_[k] * finv_[n - k];
    }
    constexpr T fact(int n) const noexcept {
        if (n < 0) return 0;
        return fact_[n];
    }
    constexpr T inv(int n) const noexcept {
        if (n < 0) return 0;
        return inv_[n];
    }
    constexpr T finv(int n) const noexcept {
        if (n < 0) return 0;
        return finv_[n];
    }
};
 
int dx[] = { 0, 1, -1, 0, 1, -1, 1, -1 };  // i<4:4way i<8:8way
int dy[] = { 1, 0, 0, -1, 1, -1, -1, 1 };
 
ll PowMod(ll n, ll k, ll mod) {
    ll r = 1;
 
    for (; k > 0; k >>= 1) {
        if (k & 1) {
            r = (r * n) % mod;
        }
        n = (n * n) % mod;
    }
    return r;
}
ll Gcd(ll a, ll b) {
    return b != 0 ? Gcd(b, a % b) : a;
}
ll Lcm(ll a, ll b) {
    return a / Gcd(a, b) * b;
}
vector<string> Split(string s, string t) {
    vector<string> v;
    int p = s.find(t);
    while (p != s.npos) {
        v.emplace_back(s.substr(0, p));
        s = s.substr(p + (int)t.size());
        p = s.find(t);
    }
    v.emplace_back(s);
    return v;
}
vector<int> Lis(const vector<int>& a) {
    #define Index_of(as, x) distance(as.begin(), lower_bound(as.begin(), as.end(),x))
//#define Index_of(as, x) \
  distance(as.begin(), upper_bound(as.begin(), as.end(), x))
    const int n = a.size();
    vector<int> A(n, INF);
    vector<int> id(n);
    for (int i = 0; i < n; ++i) {
        id[i] = Index_of(A, a[i]);
        A[id[i]] = a[i];
    }
    int m = *max_element(id.begin(), id.end());
    vector<int> b(m + 1);
    for (int i = n - 1; i >= 0; --i)
        if (id[i] == m) b[m--] = a[i];
    return b;
}
string ReplaceString(string s, string target, string replacestring) {
    string::size_type Pos(s.find(target));
 
    while (Pos != string::npos) {
        s.replace(Pos, target.length(), replacestring);
        Pos = s.find(target, Pos + replacestring.length());
    }
 
    return s;
}
string LcsAlphabeticalMinOrder(string a, string b) {
    if (a.size() < b.size()) {
        swap(a, b);
    }
 
    int n = a.size(), m = b.size();
 
    vector<string> dp(m + 1);
 
    for (int i = 0; i < n; i++) {
        vector<string> to(m + 1);
        for (int j = 0; j < m; j++) {
            if (a[i] == b[j]) {
                to[j + 1] = dp[j] + a[i];
            }
            else {
                if (to[j].size() > dp[j + 1].size()) {
                    to[j + 1] = to[j];
                }
                else if (to[j].size() < dp[j + 1].size()) {
                    to[j + 1] = dp[j + 1];
                }
                else if (to[j] < dp[j + 1]) {
                    to[j + 1] = to[j];
                }
                else {
                    to[j + 1] = dp[j + 1];
                }
            }
        }
        dp.swap(to);
    }
    return dp[m];
}
string Lcs(const string& s, const string& t) {
    int dp[3001][3001];
    int n = s.size();
    int m = t.size();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    string ans = "";
    int i = s.size(), j = t.size();
    while (i > 0 && j > 0) {
        if (s[i - 1] == t[j - 1]) {
            ans += s[i - 1];
            i--;
            j--;
        }
        else if (dp[i - 1][j] >= dp[i][j - 1])
            i--;
        else
            j--;
    }
    reverse(ans.begin(), ans.end());
    return ans;
}
vector<int> LcsInteger(const vector<int>& a, const vector<int>& b) {
#define index_of(as, x) \
  distance(as.begin(), lower_bound(as.begin(), as.end(), x))
    struct node {
        int value;
        node* next;
        node(int value, node* next) : value(value), next(next) {}
    };
    const int n = a.size(), m = b.size();
    map<int, vector<int>> M;
    for (int j = m - 1; j >= 0; --j) M[b[j]].push_back(j);
    vector<int> xs(n + 1, INF);
    xs[0] = -INF;
    vector<node*> link(n + 1);
    for (int i = 0; i < n; ++i) {
        if (M.count(a[i])) {
            vector<int> ys = M[a[i]];
            for (int j = 0; j < (int)ys.size(); ++j) {
                int k = index_of(xs, ys[j]);
                xs[k] = ys[j];
                link[k] = new node(b[ys[j]], link[k - 1]);
            }
        }
    }
    vector<int> c;
    int l = index_of(xs, INF - 1) - 1;
    for (node* p = link[l]; p; p = p->next) c.push_back(p->value);
    reverse(c.begin(), c.end());
    return c;
}
bool IsPrime(ll n) {
    if (n < 2) return false;
    for (ll i = 2; i * i <= n; i++)
        if (!(n % i)) return false;
    return true;
}
vector<ll> Eratosthenes(int n) {
    vector<ll> res;
    vector<bool> Prime(n + 1, true);
    Prime[0] = Prime[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (Prime[i]) {
            for (int j = 2; i * j <= n; j++) {
                Prime[i * j] = false;
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        if (Prime[i]) {
            res.emplace_back(i);
        }
    }
    return res;
}
ll maxSubArraySum(vector<ll> a,int left,int right) {
    //[left,right)
    int size=a.size(); 
    ll max_so_far = -LONGINF, max_ending_here = 0; 
  
    for (int i = left; i < right; i++) { 
        max_ending_here = max_ending_here + a[i]; 
        if (max_so_far < max_ending_here) {
            max_so_far = max_ending_here; 
        }
  
        if (max_ending_here < 0) {
            max_ending_here = 0; 
        }
    } 
    return max_so_far; 
} 
ll MergeCount(vector<int>& a) {
    ll count = 0;
    int n = a.size();
    if (n > 1) {
        vector<int> b(a.begin(), a.begin() + n / 2);
        vector<int> c(a.begin() + n / 2, a.end());
        count += MergeCount(b);
        count += MergeCount(c);
        for (int i = 0, j = 0, k = 0; i < n; ++i)
            if (k == (int)c.size())
                a[i] = b[j++];
            else if (j == (int)b.size())
                a[i] = c[k++];
            else if (b[j] <= c[k])
                a[i] = b[j++];
            else {
                a[i] = c[k++];
                count += n / 2 - j;
            }
    }
    return count;
}
bool WarshallFloyd(vector<vector<ll>>& c) {
    int V = c.size();
    for (int i = 0; i < V; i++) {
        c[i][i] = 0;
    }
 
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            for (int k = 0; k < V; k++) {
                if (c[j][k] > c[j][i] + c[i][k]) {
                    if(c[j][i] != INF && c[i][k] != INF){
                        c[j][k] = c[j][i] + c[i][k];
                    }
                }
            }
        }
    }
 
    for (int i = 0; i < V; i++) {
        if (c[i][i] < 0) {
            return false;
        }
    }
 
    return true;
}
vector<ll> Dijkstra(int i, vector<vector<edge>> graph) {
    int n = graph.size();
    vector<ll> d(n, LONGINF);
    d[i] = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>>
        q;
    q.push(make_pair(0, i));
    while (!q.empty()) {
        pair<ll, int> p = q.top();
        q.pop();
        int v = p.second;
        if (d[v] < p.first) {
            continue;
        }
        for (auto x : graph[v]) {
            if (d[x.to] > d[v] + x.cost) {
                d[x.to] = d[v] + x.cost;
                q.push(make_pair(d[x.to], x.to));
            }
        }
    }
    return d;
}
bool BellmanFord(int start, int V, int E, vector<edge> Edge, vector<ll>& d) {
    resize(d, V);
    fill(d.begin(), d.end(), LONGINF);
    d[start] = 0;
    vector<bool> t(V, false);
    for (int i = 0; i < V - 1; i++) {
        for (int j = 0; j < E; j++) {
            edge e = Edge[j];
            if (d[e.from] == LONGINF) {
                continue;
            }
            if (d[e.to] > d[e.from] + e.cost) {
                d[e.to] = d[e.from] + e.cost;
            }
        }
    }
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < E; j++) {
            edge e = Edge[j];
            if (d[e.from] == LONGINF) {
                continue;
            }
            if (d[e.to] > d[e.from] + e.cost) {
                d[e.to] = d[e.from] + e.cost;
                t[e.to] = true;
                /*
                if (i == V - 1) {
                        return false;
                }
                */
            }
            if (t[e.from]) {
                t[e.to] = true;
            }
        }
    }
 
    if (t[V - 1]) {
        return false;
    }
 
    return true;
}
bool TopologicalSort(const vector<vector<edge>>& g, vector<int>& ans) {
    int n = g.size(), k = 0;
    vector<int> ord(n), in(n);
    for (auto& es : g) {
        for (auto& e : es) {
            in[e.to]++;
        }
    }
    queue<int> q;
    for (int i = 0; i < n; ++i) {
        if (in[i] == 0) q.push(i);
    }
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        ord[k++] = v;
        for (auto& e : g[v]) {
            if (--in[e.to] == 0) q.push(e.to);
        }
    }
    ans = ord;
    if (*max_element(in.begin(), in.end()) == 0) {
        return true;
    }
    return false;
}
vector<int> ArticulationNode(const vector<vector<edge>>& g) {
    int n = g.size(), idx;
    vector<int> low(n), ord(n), art;
    function<void(int)> DFS = [&](int v) {
        low[v] = ord[v] = ++idx;
        for (auto& e : g[v]) {
            int w = e.to;
            if (ord[w] == 0) {
                DFS(w);
                low[v] = min(low[v], low[w]);
                if ((ord[v] == 1 && ord[w] != 2) || (ord[v] != 1 && low[w] >= ord[v])) {
                    art.push_back(v);
                }
            }
            else {
                low[v] = min(low[v], ord[w]);
            }
        }
    };
    for (int u = 0; u < n; u++) {
        if (ord[u] == 0) {
            idx = 0;
            DFS(u);
        }
    }
 
    sort(art.begin(), art.end());
    art.erase(unique(art.begin(), art.end()),
        art.end());
 
    return art;
}
vector<vector<edge>> ToRootTree(const vector<vector<edge>>& g, int r) {
    int n = g.size();
    vector<vector<edge>> G(n);
    vector<int> ord(n, -1);
 
    queue<int> q;
 
    q.push(r);
    int k = 0;
 
    while (q.size()) {
        int u = q.front();
        q.pop();
 
        for (auto& e : g[u]) {
            int v = e.to;
            if (ord[v] == -1) {
                ord[v] = k;
                k++;
                q.push(v);
                G[u].emplace_back(e);
            }
        }
    }
 
    return G;
}
edge TreeDiameter(const vector<vector<edge>>& g) {
 
    int start = 0;
 
    static const auto bfs = [](const vector<vector<edge>>& g, int s,
        queue<int>& q, vector<ll>& dist) {
            while (!q.empty()) {
                q.pop();
            }
            q.push(s);
            int n = g.size();
            dist.assign(n, LONGINF);
            dist[s] = 0;
            while (q.size()) {
                int u = q.front();
                q.pop();
                for (auto& e : g[u]) {
                    int v = e.to;
                    if (dist[v] == LONGINF) {
                        dist[v] = dist[u] + e.cost;
                        q.push(v);
                    }
                }
            }
            return dist;
    };
    vector<ll> dist;
    queue<int> q;
    bfs(g, start, q, dist);
    int n = g.size(), u = -1, v = -1;
    for (int i = 0; i < n; i++)
        if (dist[i] != LONGINF && (u == -1 || dist[i] > dist[u])) u = i;
    bfs(g, u, q, dist);
    for (int i = 0; i < n; i++)
        if (dist[i] != LONGINF && (v == -1 || dist[i] > dist[v])) v = i;
    ll d = dist[v];
    if (u > v) swap(u, v);
    return edge(u, v, d);
}
void add_edge(vector<vector<edge>>& g, int a, int b, ll cost, ll cap) {
    g[a].emplace_back(a, b, cost, cap);
    g[b].emplace_back(b, a, cost, cap);
}
pair<vector<int>, vector<edge>> bridge(const vector<vector<edge>>& g) {
    const int n = g.size();
    int idx = 0, s = 0, t = 0, k = 0;
    vector<int> ord(n, -1), onS(n), stk(n), roots(n), cmp(n);
    vector<edge> brdg;
    function<void(int, int)> dfs = [&](int v, int u) {
        ord[v] = idx++;
        stk[s++] = v;
        onS[v] = true;
        roots[t++] = v;
        for (auto& e : g[v]) {
            int w = e.to;
            if (ord[w] == -1) {
                dfs(w, v);
            }
            else if (u != w && onS[w]) {
                while (ord[roots[t - 1]] > ord[w]) {
                    --t;
                }
            }
        }
        if (v == roots[t - 1]) {
            brdg.emplace_back(u, v, 0);
            while (1) {
                int w = stk[--s];
                onS[w] = false;
                cmp[w] = k;
                if (v == w) break;
            }
            --t;
            ++k;
        }
    };
    for (int u = 0; u < n; u++) {
        if (ord[u] == -1) {
            dfs(u, n);
            brdg.pop_back();
        }
    }
    return make_pair(cmp, brdg);
}
 
class UnionFind {
private:
    std::vector<int> parent;
    std::vector<int> height;
    std::vector<int> m_size;
    int forest_num;
 
public:
    UnionFind(int size_) : parent(size_), height(size_, 0), m_size(size_, 1) {
        forest_num = size_;
        for (int i = 0; i < size_; ++i) parent[i] = i;
    }
    void init(int size_) {
        parent.resize(size_);
        height.resize(size_, 0);
        m_size.resize(size_, 1);
        forest_num = size_;
        for (int i = 0; i < size_; ++i) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        int t = size(x) + size(y);
        m_size[x] = m_size[y] = t;
        if (height[x] < height[y])
            parent[x] = y;
        else
            parent[y] = x;
        if (height[x] == height[y]) ++height[x];
        forest_num--;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) {
        if (parent[x] == x) return m_size[x];
        return size(parent[x] = find(parent[x]));
    }
    int forest() { return forest_num; }

};
class Dinic {
private:
    int n, s, t;
    vector<int> level, prog, que;
    vector<vector<ll>> cap, flow;
    vector<vector<int>> g;
    ll inf;
 
public:
    Dinic(const vector<vector<edge>>& graph)
        : n(graph.size()),
        cap(n, vector<ll>(n)),
        flow(n, vector<ll>(n)),
        g(n, vector<int>()),
        inf(LONGINF) {
        for (int i = 0; i < n; i++) {
            for (auto& e : graph[i]) {
                int u = e.from, v = e.to;
                ll c = e.capa;
                cap[u][v] += c;
                cap[v][u] += c;
                flow[v][u] += c;
                g[u].push_back(v);
                g[v].push_back(u);
            }
        }
    }
    inline ll residue(int u, int v) { return cap[u][v] - flow[u][v]; }
    ll solve(int s_, int t_) {
        this->t = t_, this->s = s_;
        que.resize(n + 1);
        ll res = 0;
        while (levelize()) {
            prog.assign(n, 0);
            res += augment(s, inf);
        }
        return res;
    }
    bool levelize() {
        int l = 0, r = 0;
        level.assign(n, -1);
        level[s] = 0;
        que[r++] = s;
        while (l != r) {
            int v = que[l++];
            if (v == t) break;
            for (const int& d : g[v])
                if (level[d] == -1 && residue(v, d) != 0) {
                    level[d] = level[v] + 1;
                    que[r++] = d;
                }
        }
        return level[t] != -1;
    }
    ll augment(int v, ll lim) {
        ll res = 0;
        if (v == t) return lim;
        for (int& i = prog[v]; i < (int)g[v].size(); i++) {
            const int& d = g[v][i];
            if (residue(v, d) == 0 || level[v] >= level[d]) continue;
            const ll aug = augment(d, min(lim, residue(v, d)));
            flow[v][d] += aug;
            flow[d][v] -= aug;
            res += aug;
            lim -= aug;
            if (lim == 0) break;
        }
        return res;
    }
};
class MinimumCostFlow {
private:
    using Flow = ll;
    using Cost = ll;
    struct Edge {
        int d;
        Flow c, f;
        Cost w;
        int r, is_r;
        Edge(int d_, Flow c_, Flow f_, Cost w_, int r_, bool is_r_)
            : d(d_), c(c_), f(f_), w(w_), r(r_), is_r(is_r_) {}
    };
    int n;
    vector<vector<Edge>> g;
 
public:
    MinimumCostFlow(int n_) : n(n_), g(vector<vector<Edge>>(n_)) {}
 
    void add_edge(int src, int dst, Cost cost,Flow cap) {
        int rsrc = g[dst].size();
        int rdst = g[src].size();
        g[src].emplace_back(dst, cap, 0, cost, rsrc, false);
        g[dst].emplace_back(src, cap, cap, -cost, rdst, true);
    }
 
    Cost solve(int s, int t, Flow f) {
        Cost res = 0;
 
        vector<Cost> h(n + 10), dist(n);
        vector<int> prevv(n + 10), preve(n + 10);
 
        using pcv = pair<Cost, int>;
        priority_queue<pcv, vector<pcv>, greater<pcv>> q;
        fill(h.begin(), h.end(), 0);
        while (f > 0) {
            fill(dist.begin(), dist.end(), LONGINF);
            dist[s] = 0;
            q.emplace(0, s);
            while (q.size()) {
                Cost cd;
                int v;
                tie(cd, v) = q.top();
                q.pop();
                if (dist[v] < cd) continue;
                for (int i = 0; i < (int)(g[v].size()); ++i) {
                    Edge& e = g[v][i];
                    if (residue(e) == 0) continue;
                    if (dist[e.d] + h[e.d] > cd + h[v] + e.w) {
                        dist[e.d] = dist[v] + e.w + h[v] - h[e.d];
                        prevv[e.d] = v;
                        preve[e.d] = i;
                        q.emplace(dist[e.d], e.d);
                    }
                }
            }
 
            if (dist[t] == LONGINF) return -1;
 
            for (int i = 0; i < n; ++i) h[i] += dist[i];
            Flow d = f;
            for (int v = t; v != s; v = prevv[v]) {
                chmin(d, residue(g[prevv[v]][preve[v]]));
            }
            f -= d;
            res += d * h[t];
            for (int v = t; v != s; v = prevv[v]) {
                Edge& e = g[prevv[v]][preve[v]];
                e.f += d;
                g[v][e.r].f -= d;
            }
        }
        return res;
    }
 
    Flow residue(const Edge& e) { return e.c - e.f; }
 
    void show() {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < (int)(g[i].size()); ++j) {
                Edge& e = g[i][j];
                if (e.is_r) continue;
                cout << i << "->" << e.d << "(flow:" << e.f << ")" << endl;
            }
        }
    }
};
class BipartiteMatching {
private:
    int V;
    vector<int> match;
    vector<bool> used;
    vector<vector<int>> g;
    vector<pair<int, int>> match_pair;
 
    bool dfs(int v) {
        used[v] = true;
        for (int i = 0; i < (int)g[v].size(); i++) {
            int u = g[v][i];
            int w = match[u];
            if (w < 0 || !used[w] && dfs(w)) {
                match[v] = u;
                match[u] = v;
                match_pair.emplace_back(make_pair(u, v));
                return true;
            }
        }
        return false;
    }
 
public:
    BipartiteMatching(int n) {
        V = n;
        resize(match, n);
        resize(used, n);
        resize(g, n);
    }
 
    void add_edge(int u, int v) {
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
 
    int MatchingSolve() {
        int res = 0;
        fill(match.begin(), match.end(), -1);
 
        for (int v = 0; v < V; v++) {
            if (match[v] < 0) {
                fill(used.begin(), used.end(), false);
                if (dfs(v)) {
                    res++;
                }
            }
        }
        return res;
    }
 
    vector<pair<int, int>> get_pair() {
        for (auto x : match_pair) {
            cout << x.first << "  " << x.second << endl;
        }
        return match_pair;
    }
};
class Lca {
private:
    int n;
    int log2_n;
    vector<vector<int>> parent;
    vector<int> depth;
    
    void dfs(const vector<vector<edge>>& g, int v, int p, int d) {
        parent[0][v] = p;
        depth[v] = d;
        for (auto& e : g[v]) {
            if (e.to != p) {
                dfs(g, e.to, v, d + 1);
            }
        }
    }
 
public:
    Lca(const vector<vector<edge>>& g, int root) {
        n = g.size();
        log2_n = (int)log2(n) + 1;
        resize(parent, log2_n, n);
        resize(depth, n);
 
        dfs(g, root, -1, 0);
 
        for (int k = 0; k + 1 < log2_n; k++) {
            for (int v = 0; v < (int)g.size(); v++) {
                if (parent[k][v] < 0) {
                    parent[k + 1][v] = -1;
                }
                else {
                    parent[k + 1][v] = parent[k][parent[k][v]];
                }
            }
        }
    }
 
    int get_lca(int u, int v) {
        if (depth[u] > depth[v]) {
            swap(u, v);
        }
 
        for (int k = 0; k < log2_n; k++) {
            if ((depth[v] - depth[u]) >> k & 1) {
                v = parent[k][v];
            }
        }
        if (u == v) {
            return u;
        }
 
        for (int k = log2_n - 1; k >= 0; k--) {
            if (parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }
 
    int get_depth(int v) { return depth[v]; }
};
class DAG {
private:
    int n;
    vector<vector<edge>> g;
    vector<int> visited;
    vector<int> dp;
    vector<int> topological;
 
    int dfs(int s) {
        if ((int)g[s].size() == 0) {
            return 1;
        }
        if (dp[s] > 0) {
            return dp[s];
        }
 
        int mx = 1;
        for (auto j : g[s]) {
            if (visited[j.to] == 0) {
                visited[j.to] = 1;
                int l = 0;
                l = dfs(j.to);
                chmax(mx, l);
            }
            else {
                chmax(mx, dp[j.to]);
            }
        }
        return dp[s] = mx + 1;
    }
 
public:
    DAG(const vector<vector<edge>>& f) {
        g = f;
        n = f.size();
        resize(visited, n + 1);
        fill(visited.begin(), visited.end(), 0);
        resize(dp, n + 1);
        fill(dp.begin(), dp.end(), -1);
        resize(topological, n);
    }
    DAG(int x) {
        n = x;
        resize(g, n);
        resize(visited, n + 1);
        fill(visited.begin(), visited.end(), 0);
        resize(dp, n + 1);
        fill(dp.begin(), dp.end(), -1);
    }
 
    void add_edge(int a, int b) { g[a].emplace_back(a, b); }
    void add_edge(int a, int b, ll c) { g[a].emplace_back(a, b, c); }
    void add_edge(int a, int b, ll c, ll d) { g[a].emplace_back(a, b, c, d); }
 
    int longest_path() {
        int mx = -1;
        for (int i = 0; i < n; i++) {
            int h = 0;
            if (visited[i] == 0) {
                h = dfs(i);
                chmax(mx, h);
            }
        }
        return mx - 1;
    }
 
    bool TopologicalSort() {
        int k = 0;
        vector<int> ord(n), in(n);
        for (auto& es : g) {
            for (auto& e : es) {
                in[e.to]++;
            }
        }
        queue<int> q;
        for (int i = 0; i < n; ++i) {
            if (in[i] == 0) q.push(i);
        }
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            ord[k++] = v;
            for (auto& e : g[v]) {
                if (--in[e.to] == 0) {
                    q.push(e.to);
                }
            }
        }
        topological = ord;
        if (*max_element(in.begin(), in.end()) == 0) {
            return true;
        }
        return false;
    }

    vector<int> getTopologicalArray(){
        return topological;
    }
};
class RangeMinimumUpdateQuerySegmentTree {
private:
    int n;
    ll inf = (1LL << 31) - 1;  // 2^31-1
    vector<ll> dat, lazy;
 
    void eval(int len, int k) {
        if (lazy[k] == inf) return;
        if (k * 2 + 1 < n * 2 - 1) {
            lazy[2 * k + 1] = lazy[k];
            lazy[2 * k + 2] = lazy[k];
        }
        dat[k] = lazy[k];
        lazy[k] = inf;
    }
 
public:
    RangeMinimumUpdateQuerySegmentTree() {}
    RangeMinimumUpdateQuerySegmentTree(int n_) {
        n = 1;
        while (n < n_) n *= 2;
        dat.assign(n * 2, inf);
        lazy.assign(n * 2, inf);
    }
 
    // [a,b)
    ll update(int a, int b, ll x, int k, int l, int r) {
        eval(r - l, k);
        if (b <= l || r <= a) return dat[k];
        if (a <= l && r <= b) {
            lazy[k] = x;
            return lazy[k];
        }
        return dat[k] = min(update(a, b, x, 2 * k + 1, l, (l + r) / 2),
            update(a, b, x, 2 * k + 2, (l + r) / 2, r));
    }
    ll update(int a, int b, ll x) { return update(a, b, x, 0, 0, n); }
 
    // [a, b)
    ll query(int a, int b, int k, int l, int r) {
        eval(r - l, k);
        if (b <= l || r <= a) return inf;
        if (a <= l && r <= b) return dat[k];
        ll vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
        ll vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
        return min(vl, vr);
    }
    ll query(int a, int b) { return query(a, b, 0, 0, n); }
};
class RangeSumQuerySegmentTree {
private:
    struct Node {
        Node* left, * right;
        ll v;
 
        Node() : left(nullptr), right(nullptr), v(0) {}
    };
    Node* root;
    ll n, n0;
    ll query(ll a, ll b, Node* n, ll l, ll r) {
        if (a <= l && r <= b) {
            return n->v;
        }
        if (r <= a || b <= l) {
            return 0;
        }
 
        ll lv = n->left ? query(a, b, n->left, l, (l + r) >> 1) : 0;
        ll rv = n->right ? query(a, b, n->right, (l + r) >> 1, r) : 0;
        return (lv + rv) % MOD;
    }
 
public:
    RangeSumQuerySegmentTree(ll n) : n(n) {
        n0 = 1;
        while (n0 < n) n0 <<= 1;
        root = new Node();
    }
    ~RangeSumQuerySegmentTree() {
        delete root;
        root = nullptr;
    }
 
    void update(ll k, ll x) {
        Node* n = root;
        ll l = 0, r = n0;
        n->v = (n->v + x) % MOD;
        while (r - l > 1) {
            ll m = (l + r) >> 1;
            if (k < m) {
                if (!n->left) n->left = new Node();
                n = n->left;
 
                r = m;
            }
            else {
                if (!n->right) n->right = new Node();
                n = n->right;
 
                l = m;
            }
            n->v = (n->v + x) % MOD;
        }
    }
 
    ll query(ll a, ll b) { return query(a, b, root, 0, n0); }
 
    ll lquery(ll b) { return query(0, b, root, 0, n0); }
 
    ll rquery(ll a) { return query(a, n0, root, 0, n0); }
};
class KDimensionalTree {
public:
    struct Node {
        int location;
        int p, l, r;
        Node() {}
    };
    struct Point {
        int id, x, y;
        Point() {}
        Point(int i, int a, int b) {
            id = i;
            x = a;
            y = b;
        }
        bool operator<(const Point& p) const { return id < p.id; }
        void print() { cout << id << endl; }
    };
    static const ll NIL = -1;
    static bool lessX(const Point& p1, const Point& p2) { return p1.x < p2.x; }
    static bool lessY(const Point& p1, const Point& p2) { return p1.y < p2.y; }
 
    int N;
    vector<Point> P;
    vector<Node> T;
    int np;
 
    KDimensionalTree() {}
    KDimensionalTree(int N) { init(N); }
 
    void init(int n) {
        N = n;
        P.clear();
        T.clear();
        resize(P, N);
        resize(T, N);
        np = 0;
    }
 
    int makeKDTree(int l, int r, int depth) {
        if (l >= r) {
            return NIL;
        }
        int mid = (l + r) / 2;
        int t = np++;
        if (depth & 1) {
            sort(P.begin() + l, P.begin() + r, lessY);
        }
        else {
            sort(P.begin() + l, P.begin() + r, lessX);
        }
        T[t].location = mid;
        T[t].l = makeKDTree(l, mid, depth + 1);
        T[t].r = makeKDTree(mid + 1, r, depth + 1);
        return t;
    }
    void find(int v, int sx, int tx, int sy, int ty, int depth,
        vector<Point>& ans) {
        int x = P[T[v].location].x;
        int y = P[T[v].location].y;
        if (sx <= x && x <= tx && sy <= y && y <= ty) {
            ans.push_back(P[T[v].location]);
        }
        if (depth % 2 == 0) {
            if (T[v].l != NIL) {
                if (sx <= x) find(T[v].l, sx, tx, sy, ty, depth + 1, ans);
            }
            if (T[v].r != NIL) {
                if (x <= tx) find(T[v].r, sx, tx, sy, ty, depth + 1, ans);
            }
        }
        else {
            if (T[v].l != NIL) {
                if (sy <= y) find(T[v].l, sx, tx, sy, ty, depth + 1, ans);
            }
            if (T[v].r != NIL) {
                if (y <= ty) find(T[v].r, sx, tx, sy, ty, depth + 1, ans);
            }
        }
    }
    void add_point(int i, int x, int y) {
        P[i].id = i;
        P[i].x = x;
        P[i].y = y;
        T[i].l = T[i].r = T[i].p = NIL;
    }
};
class RangeAddQuerySegmentTree {
private:
    int n;
    vector<ll> data;
 
public:
    RangeAddQuerySegmentTree() {}
    RangeAddQuerySegmentTree(int N) {
        n = N;
        resize(data, n + 1);
        fill(data.begin(), data.end(), 0);
    }
 
    void add(int i, ll x) {
        while (i) {
            data[i] += x;
            i -= (i & -i);
        }
    }
    void add(int i, int j, ll x) {
        add(j, x);
        add(i - 1, -x);
    }
 
    ll get(int i) {
        ll res = 0;
        while (i <= n) {
            res += data[i];
            i += (i & -i);
        }
        return res;
    }
};
class RangeSumAddQuerySegmentTree {
private:
    vector<ll> bit0, bit1;
    int n;
 
    ll sum(const vector<ll>& b, int i) {
        ll s = 0;
        while (i > 0) {
            s += b[i];
            i -= (i & -i);
        }
        return s;
    }
 
    void add(vector<ll>& b, int i, ll v) {
        while (i <= n) {
            b[i] += v;
            i += (i & -i);
        }
    }
 
public:
    RangeSumAddQuerySegmentTree() {}
    RangeSumAddQuerySegmentTree(int N) {
        n = N;
        resize(bit0, n + 1);
        resize(bit1, n + 1);
        fill(bit0.begin(), bit0.end(), 0);
        fill(bit1.begin(), bit1.end(), 0);
    }
 
    void update(int l, int r, ll x) {
        add(bit0, l, -x * (l - 1));
        add(bit1, l, x);
        add(bit0, r + 1, x * r);
        add(bit1, r + 1, -x);
    }
 
    ll query(int l, int r) {
        ll res = 0;
        res += sum(bit0, r) + sum(bit1, r) * r;
        res -= sum(bit0, l - 1) + sum(bit1, l - 1) * (l - 1);
        return res;
    }
};



long double cross(const complex<long double> &a, const complex<long double> &b) { return a.real() * b.imag() - a.imag() * b.real(); }
long double dot(const complex<long double> &a, const complex<long double> &b) { return a.real() * b.real() + a.imag() * b.imag(); }

pair<long double,complex<long double>> smallest_enclosing_disc(vector<complex<long double>> ps){
    const long double pi = 3.1415926535897932384626;
    static const long double eps = 1e-10;
    static const long double inf = 1e12;

    #define rad first
    #define pnt second

    using circle = pair<complex<long double>, long double>;

    auto c3 = [](const complex<long double> &a, const complex<long double> &b, const complex<long double> &c){
        long double A = norm(b - c);
        long double B = norm(c - a);
        long double C = norm(a - b);
        long double S = abs(cross(b - a, c - a));
        complex<long double> p = (A*(B+C-A)*a + B*(C+A-B)*b + C*(A+B-C)*c) / (4*S*S);
        long double r = abs(p - a);
        return make_pair(r, p);
    };

    auto c2 = [](const complex<long double> &a, const complex<long double> &b){
        complex<long double> c = (a + b) / (long double)2;
        long double r = abs(a - c);
        return make_pair(r, c);
    };

    auto in_circle = [](const complex<long double> &a, const pair<long double, complex<long double>> &c){
        return norm(a - c.pnt) <= c.rad*c.rad + eps;
    };

    int n = ps.size();
    random_shuffle(ps.begin(), ps.end());
    pair<long double, complex<long double>> c = c2(ps[0], ps[1]);
    for(int i = 2; i < n; ++i){
        if(!in_circle(ps[i], c)){
            c = c2(ps[0], ps[i]);
            for(int j = 1; j < i; ++j){
                if(!in_circle(ps[j], c)){
                    c = c2(ps[j], ps[i]);
                    for(int k = 0; k < j; ++k){
                        if(!in_circle(ps[k], c)){
                            c = c3(ps[i], ps[j], ps[k]);
                        }
                    }
                }
            }
        }
    }
    return c;
}

pair<ll, vector<edge>> Prim_minimumSpanningTree(const vector<vector<edge>> &g, int r,int K) {
  int n = g.size();
  vector<edge> T;
  ll total = 0;

  vector<bool> visited(n);
  priority_queue<edge> Q;
  Q.push( edge(-1, r, 0,0));
  ll ans=0;
  int k=0;
  while (!Q.empty()) {
    edge e = Q.top(); Q.pop();
    if (visited[e.to]) continue;
    T.push_back(e);
    total += e.cost;
    ans=max(ans,-e.cost);
    k++;
    if(k==K){
        break;
    }
    visited[e.to] = true;
    for(auto f:g[e.to]) if (!visited[f.to]) Q.push(f);
  }
  return pair<ll, vector<edge>>(ans, T);
}




int main() {
    int n,q;cin>>n>>q;
    vector<pair<ll,ll>> xw(n);
    for(int i=0;i<n;i++){
        cin>>xw[i].first>>xw[i].second;
    }
    sort(xw.begin(),xw.end());
    /*
    vector<ll> X(n+1),W(n+1);

    for(int i=0;i<n;i++){
        X[i+1]=xw[i].first;
        W[i+1]=xw[i].second;
    }
    for(int i=1;i<n+1;i++){
        X[i]+=X[i-1];
        W[i]+=W[i-1];
    }
    */
    vector<pair<ll,ll>> query(q);
    for(int i=0;i<q;i++){
        cin>>query[i].first;
        query[i].second=i;
    }
    sort(query.begin(),query.end());
    vector<pair<ll,ll>> ans(q);

    for(int i=0;i<q;i++){
        ans[i].second=query[i].second;
    }


    ll leftAns=0;
    ll leftHeavy=0;
    ll rightHeavy=0;
    ll leftK=0;
    ll rightK=0;
    ll check_i=-1;//左右の狭間
    ll leftOldQueryAns=0;
    ll rightOldQueryAns=0;

    for(int i=0;i<n;i++){
        if(query[0].first>=xw[i].first){
            leftHeavy+=xw[i].second;
            check_i=i;
            leftAns+=abs(xw[i].first-query[0].first)*xw[i].second;
            leftOldQueryAns+=abs(xw[i].first-query[0].first)*xw[i].second;
            leftK++;
        }
        else{
            rightHeavy+=xw[i].second;
            leftAns+=abs(xw[i].first-query[0].first)*xw[i].second;
            rightOldQueryAns+=abs(xw[i].first-query[0].first)*xw[i].second;
            rightK++;
        }
    }
    /*

    for(int i=1;i<q;i++){
        int tmp=upper_bound(ALL(xw),make_pair(query[i].first,LONGINF))-xw.begin();
        ll check=0;
        ll left=leftHeavy*abs(query[i].first-query[i-1].first);
        while(check_i<tmp){
            rightHeavy-=xw[check_i].second;
            leftHeavy+=xw[check_i].second;
            leftK++;
            rightK--;
            rightOldQueryAns-=xw[check_i].second*abs(query[i-1].first-xw[check_i].first);
            check+=abs(query[i].first-xw[check_i].first)*xw[check_i].second;
            check_i++;
        }
        ll right=rightOldQueryAns-rightHeavy*abs(query[i].first-query[i-1].first);
        cout<<left+right+check<<endl;
    }
    */
    ans[0].first=leftAns;
    check_i++;
    for(int i=1;i<q;i++){
        ll tmp=0;
        ll left=leftHeavy*abs(query[i].first-query[i-1].first);
        //leftOldQueryAns=left;

        while(check_i<n&&query[i].first>=xw[check_i].first){
            rightHeavy-=xw[check_i].second;
            leftHeavy+=xw[check_i].second;
            leftK++;
            rightK--;
            tmp+=abs(query[i].first-xw[check_i].first)*xw[check_i].second;
            tmp-=abs(query[i-1].first-xw[check_i].first)*xw[check_i].second;
            check_i++;
        }

        ll right=rightHeavy*abs(query[i].first-query[i-1].first);
        //rightOldQueryAns=right;
        //leftOldQueryAns+=tmp;

        //cout<<leftOldQueryAns<<" "<<tmp<<" "<<rightOldQueryAns<<endl;
        //cout<<left<<" "<<tmp<<" "<<right<<" "<<leftHeavy<<" "<<rightHeavy<<endl;
        ans[i].first=ans[i-1].first+tmp+left-right;
        //ans[i].first=ans[i-1].firstrightOldQueryAns+leftOldQueryAns;
    }
    /*
    vector<ll> ANS(q);
    for(int i=0;i<q;i++){
        ll tmp=0;
        for(int j=0;j<n;j++){
            tmp+=abs(xw[j].first-query[i].first)*xw[j].second;
        }
        ANS[i]=tmp;
    }
    */

    for(int i=0;i<q;i++){
       swap(ans[i].first,ans[i].second);
    }
    sort(ans.begin(),ans.end());

    for(int i=0;i<q;i++){
        cout<<ans[i].second<<endl;
    }

    ;
    return 0;
}