/*
　Hi,I am warabi.

 Welcome to my coding space.
 Let me give you a great word of advice.

 "The pen is mightier than the sword"
            -by Edward Bulwer-Lytton

　　_,,....,,_　 ＿人人人人人人人人人人人人人人人人人人＿
-''":::::::::::::｀''＞　　　ゆっくりできるとでも?　　＜
ヽ:::::::::::::::::::::￣^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ￣
　|::::::;ノ´￣＼:::::::::::＼_,. -‐ｧ　　　　　＿_　　 _____　　 ＿_____
　|::::ﾉ　　　ヽ､ヽr-r'"´　　（.__　　　　,´　_,, '-´￣￣｀-ゝ 、_ イ、
_,.!イ_　　_,.ﾍｰｧ'二ﾊ二ヽ､へ,_7　　　'r ´　　　　　　　　　　ヽ、ﾝ、
::::::rｰ''7ｺ-‐'"´　 　 ;　 ',　｀ヽ/｀7　,'＝=─-　　　 　 -─=＝',　i
r-'ｧ'"´/　 /!　ﾊ 　ハ　 !　　iヾ_ﾉ　i　ｲ　iゝ、ｲ人レ／_ルヽｲ i　|
!イ´ ,' |　/__,.!/　V　､!__ﾊ　 ,'　,ゝ　ﾚﾘｲi (ﾋ_] 　　 　ﾋ_ﾝ ).| .|、i .||
`! 　!/ﾚi'　(ﾋ_] 　　 　ﾋ_ﾝ ﾚ'i　ﾉ　　　!Y!""　  ,＿__, 　 "" 「 !ﾉ i　|
,'　 ﾉ 　 !'"　   ,＿__,　 "' i .ﾚ'　　　　L.',. ヽ _ﾝ　　　　L」 ﾉ| .|
　（　　,ﾊ　　　　ヽ _ﾝ　 　人! 　　　　 | ||ヽ、　　　　　　 ,ｲ| ||ｲ| /
,.ﾍ,）､　　）＞,､ _____,　,.イ　 ハ　　　　レ ル｀ ー--─ ´ルﾚ　ﾚ´

　Take your time.
　
　GIVE ME AC!!!!!!!!!!!!!!!!!!!!!!!!!
　
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define V vector
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define brep(i,a,b) for(ll i=a;i>=b;i--)
#define reph(i,vec) for(auto &i:vec)
#define FI first
#define SE second
#define P pair
#define PB push_back
#define EB emplace_back
#define INS insert
#define all(vec) vec.begin(),vec.end()
#define in(name) ll name;cin >> name
#define ins(name) string name;cin >> name;
#define inc(name) char name;cin >> name
#define ing(name,size,E) vector<vector<ll>> name(size);rep(i,0,E){in(a);in(b);a--;b--;name[a].PB(b);name[b].PB(a);}
#define ing_on(name,size,E) vector<vector<long long>> name(size);rep(i,0,E){in(a);in(b);a--;b--;name[a].PB(b);}
#define ing_cost(name,size,E) vector<vector<P<ll,ll>>> name(size);rep(i,0,E){in(a);in(b);in(c);a--;b--;name[a].PB({b,c});name[b].PB({a,c});}
#define invll(name,size) vector<ll> name(size);reph(i,name)cin >> i
#define invvll(name,size1,size2) vector<vector<long long>> name(size1,vector<long long>(size2));reph(v,name)reph(i,v)cin>>i;
#define invp(name,size) vector<P<ll,ll>> name(size);for(ll i=0;i<size;i++)cin >> name[i].FI >> name[i].SE
#define out(n) cout << (n) << endl
#define _out(n) cout << " " << (n) << endl;
#define notout(n) cout << (n)
#define out_(n) cout << (n) << " "
#define set_out(n,k) cout << fixed << setprecision(k) << (n) << endl;
#define set_notout(n,k) cout << fixed << setprecision(k) << (n) << endl;
#define set_out_(n,k) cout << fixed << setprecision(k) << (n) << " ";
#define vout(vec) for(int i=0;i<vec.size();i++)cout<<(i?" ":"")<<(vec[i]);cout<<endl;
#define nel cout<<endl;
#define getbit(n,k) (((1LL<<(k))&(n))>0)

#define INF 1000000000000000000ll
#define MOD 1000000007
#define MOD2 998244353
#define CMOD MOD2
#define EPS 0.00000001

//debug
#define bug assert(false);
#define debug cout<<"OK Line "<<__LINE__<<endl;
//

//constexpr long double PI=3.14159265358979323846;

//template
template<typename T>
inline bool chmax(T& a, const T b) { if (a < b) { a = b; return true; }return false; }
template<typename T>
inline bool chmin(T& a, const T b) { if (a > b) { a = b; return true; }return false; }
//

namespace Warabi {

    //常備変数のコーナー
    V<bool> primes(1e7+5, true);
    V<ll> prime_list;
    V<ll> prime_rui(1e7+5, 0LL);
    V<bool> visiteded(300100);
    V<bool> afed(300100, false);
    V<ll> k1(200100, 0ll);
    V<ll> k2(200100, 0ll);
    //

    //常備構造体宣言のコーナー
    class UnionFind {
    private:
        ll NumberOfElements;
        ll Not1NumberOfelements;
    public:
        vector<ll> par;
        vector<ll> SIZE;

        void init(ll sz) {
            par.resize(sz, -1LL);
            SIZE.resize(sz, 1LL);
            NumberOfElements = sz;
            Not1NumberOfelements = 0ll;
        }
        ll root(ll pos) {
            if (par[pos] == -1) return pos;
            par[pos] = root(par[pos]);
            return par[pos];
        }
        bool same(ll u, ll v) {
            if (root(u) == root(v)) return true;
            return false;
        }
        ll SZ(ll u) {
            return SIZE[root(u)];
        }
        ll noe() {
            return NumberOfElements;
        }
        ll nnoe() {
            return Not1NumberOfelements;
        }
        bool unite(ll u, ll v) {
            u = root(u); v = root(v);
            if (u == v) {
                return false;
            }
            if (SZ(u) == 1LL and SZ(v) == 1LL)Not1NumberOfelements++;
            if (u < v)swap(u, v);
            par[u] = v;
            SIZE[v] += SIZE[u];
            NumberOfElements--;
            return true;
        }
    };

    class SCC {
    public:
        V<V<ll>> G;
        V<V<ll>> UG;
        V<ll> order;
        V<ll> GROUP;
        V<bool> visited;
        ll sz_count;
        V<ll> groupsize;

        void init(ll sz) {
            G.resize(sz, V<ll>(0));
            UG.resize(sz, V<ll>(0));
            GROUP.resize(sz, -1ll);
            visited.resize(sz, false);
            sz_count = 0LL;
            return;
        }

        void dfs(ll now) {
            visited[now] = true;
            reph(i, G[now]) {
                if (visited[i])continue;
                dfs(i);
            }
            order.PB(now);
            return;
        }

        void dfs2(ll now, ll group) {
            GROUP[now] = group;
            sz_count++;
            reph(i, UG[now]) {
                if (GROUP[i] != -1ll and GROUP[i] != group)continue;
                if (GROUP[i] != -1ll)continue;
                dfs2(i, group);
            }
            return;
        }

        void make_group(V<V<ll>> Graph_function) {
            G = Graph_function;
            rep(i, 0, (ll)G.size()) {
                reph(j, G[i]) {
                    UG[j].PB(i);
                }
            }
            rep(i, 0, (ll)G.size()) {
                if (visited[i])continue;
                dfs(i);
            }
            reverse(all(order));
            ll now_group = 0LL;
            reph(i, order) {
                if (GROUP[i] != -1)continue;
                ll prev = sz_count;
                dfs2(i, now_group);
                now_group++;
                groupsize.PB(sz_count - prev);
            }
            return;
        }
    };

    template<typename X, typename M>
    class SegmentTree {
    public:
        long long sz;
        using FX = function<X(X, X)>;
        using FA = function<X(X, M)>;
        using FM = function<M(M, M)>;
        const FX fx;
        const FA fa;
        const FM fm;
        const X ex;
        const M em;
        vector<X> node;
        vector<M> lazy;
        SegmentTree(long long sz_, FX fx_, FA fa_, FM fm_, X ex_, M em_) :sz(), fx(fx_), fa(fa_), fm(fm_), ex(ex_), em(em_) {
            long long n = 1LL;
            while (n < sz_)n *= 2;
            sz = n;
            node.resize(sz * 2 - 1, ex);
            lazy.resize(sz * 2 - 1, em);
        }
        void set(long long index, X x) {
            node[index + sz - 1] = x;
            return;
        }
        void build() {
            for (int i = sz - 2; i >= 0; i--)node[i] = fx(node[i * 2 + 1], node[i * 2 + 2]);
            return;
        }
        void eval(long long k) {
            if (lazy[k] == em)return;
            if (k < sz - 1) {
                lazy[k * 2 + 1] = fm(lazy[k * 2 + 1], lazy[k]);
                lazy[k * 2 + 2] = fm(lazy[k * 2 + 2], lazy[k]);
            }
            node[k] = fa(node[k], lazy[k]);
            lazy[k] = em;
        }
        void update_sub(long long a, long long b, M x, long long k, long long l, long long r) {
            //cout << " " << a << " " << b << " " << l << " " << r << endl;
            eval(k);
            if (a <= l and r <= b) {
                lazy[k] = fm(lazy[k], x);
                //cout<<" "<<lazy[k]<<endl;
                eval(k);
                return;
            }
            else if (a < r and l < b) {
                update_sub(a, b, x, k * 2 + 1, l, (l + r) / 2);
                update_sub(a, b, x, k * 2 + 2, (l + r) / 2, r);
                node[k] = fx(node[k * 2 + 1], node[k * 2 + 2]);
                return;
            }
            return;
        }
        void update(long long a, long long b, M x) {
            update_sub(a, b, x, 0LL, 0LL, sz);
            return;
        }
        void add_sub(long long a, X x, long long k, long long l, long long r) {
            eval(k);
            node[k] += x;
            if (k < sz - 1) {
                long long mid = (l + r) / 2;
                if (a < mid)add_sub(a, x, k * 2 + 1, l, mid);
                else add_sub(a, x, k * 2 + 2, mid, r);
            }
            return;
        }
        void add(long long a, X x) {
            add_sub(a, x, 0LL, 0LL, sz);
        }
        X query_sub(long long a, long long b, long long k, long long l, long long r) {
            eval(k);
            if (r <= a or b <= l)return ex;
            else if (a <= l and r <= b)return node[k];
            else {
                X Xl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
                X Xr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
                //cout<<" / "<<Xl<<" "<<Xr<<endl;
                return fx(Xl, Xr);
            }
        }
        X query(long long a, long long b) {
            return query_sub(a, b, 0LL, 0LL, sz);
        }
        inline X operator [] (long long index) {
            return query(index, index + 1);
        }
    };

    template<typename T>
    class multimap {
    private:
        map<T, ll> mp;
    public:
        void add(ll x) {
            mp[x]++;
            return;
        }
        void del(ll x) {
            mp[x]--;
            if (mp[x] < 1)mp.erase(x);
            return;
        }
        T maximum() {
            return mp.rbegin()->first;
        }
        T minimum() {
            return mp.begin()->first;
        }
    };

    class LCA {
    public:
        vector<vector<long long>> parent;
        vector<long long> dist;
        vector<vector<long long>> G;
        LCA(const vector<vector<long long>>& gr) { init(gr); }
        void dfs(long long v, long long p, long long d) {
            parent[0][v] = p;
            dist[v] = d;
            for (long long next : G[v]) {
                if (next == p)continue;
                dfs(next, v, d + 1);
            }
            return;
        }
        void init(const vector<vector<long long>>& gr) {
            G = gr;
            parent.assign(33, vector<long long>(G.size(), -1LL));
            dist.assign(G.size(), -1LL);
            dfs(0LL, -1LL, 0LL);
            for (int i = 0; i < 32; i++) {
                for (int j = 0; j < (int)G.size(); j++) {
                    if (parent[i][j] < 0LL) {
                        parent[i + 1][j] = -1LL;
                    }
                    else {
                        parent[i + 1][j] = parent[i][parent[i][j]];
                    }
                }
            }
            return;
        }
        long long lca(long long u, long long v) {
            if (dist[u] < dist[v])swap(u, v);
            long long between = dist[u] - dist[v];
            for (int i = 0; i < 33; i++) {
                if (between & (1LL << i)) { u = parent[i][u]; }
            }
            if (u == v)return u;
            for (int i = 32; i >= 0; i--) {
                if (parent[i][u] != parent[i][v]) {
                    u = parent[i][u];
                    v = parent[i][v];
                }
            }
            assert(parent[0][u] == parent[0][v]);
            return parent[0][u];
        }
        long long get_dist(long long u, long long v) {
            return dist[u] + dist[v] - 2 * dist[lca(u, v)];
        }
        bool on_path(long long u, long long v, long long a) {
            return get_dist(u, v) == get_dist(u, a) + get_dist(v, a);
        }
    };

    class nCk {
    public:
        const long long m;
        const long long MAXIMUM = 2000005;
        vector<long long> fac, facinv, inv;
        nCk(long long m_);
        ~nCk();
        long long com(long long n, long long k)const;
    };
    nCk::nCk(long long m_) :m(m_) {
        fac.resize(MAXIMUM + 3);
        facinv.resize(MAXIMUM + 3);
        inv.resize(MAXIMUM + 3);
        fac[0] = fac[1] = 1;
        facinv[0] = facinv[1] = 1;
        inv[1] = 1;
        for (long long i = 2; i < MAXIMUM + 2; i++) {
            fac[i] = fac[i - 1] * i % m;
            inv[i] = m - inv[m % i] * (m / i) % m;
            facinv[i] = facinv[i - 1] * inv[i] % m;
        }
    }
    nCk::~nCk() {}
    long long nCk::com(long long n, long long k)const {
        if (k == 0)return 1;
        if (n < k)return 0LL;
        assert(!(n < 0 || k < 0));
        return fac[n] * (facinv[k] * facinv[n - k] % m) % m;
    }

    //

    //常備構造体宣言のコーナー
    
    //


    //常備関数のコーナー
    void Yes(bool f) { cout << (f ? "Yes" : "No") << endl; }
    void YES(bool f) { cout << (f ? "YES" : "NO") << endl; }

    //木の直径を求める
    tuple<ll,ll,ll> Cdiameter(V<V<P<ll, ll>>> G, ll start, bool type) {
        visiteded = afed;
        queue<ll> sirabe;
        sirabe.push(start);
        V<ll> short_load(G.size(), 0LL);
        while (!sirabe.empty()) {
            ll s = sirabe.front();
            sirabe.pop();
            visiteded[s] = true;
            reph(i, G[s]) {
                if (visiteded[i.FI])continue;
                short_load[i.FI] = short_load[s] + i.SE;
                sirabe.push(i.FI);
            }
        }
        ll far_max = -1LL;
        ll element = -1LL;
        rep(i, 0, (ll)G.size()) {
            if (far_max >= short_load[i])continue;
            far_max = short_load[i];
            element = i;
        }
        if (type)return Cdiameter(G, element, false);
        else return { start,element,far_max };
    }
    //素数の取得
    void prime_init() {
        const int Limit=1e7+5;
        V<bool> at(Limit, true);
        primes = at;
        primes[0] = primes[1] = false;
        rep(i, 2, Limit) {
            if (!primes[i])continue;
            for (ll j = i * 2; j <= Limit; j += i)primes[j] = false;
        }
        rep(i, 1, Limit) {
            if (primes[i]) {
                prime_list.PB(i);
                prime_rui[i] = prime_rui[i - 1] + 1;
            }
            else {
                prime_rui[i] = prime_rui[i - 1];
            }
        }
        return;
    }

    //modpow
    long long modpow(long long a, long long b, long long m) {
        long long p = 1, q = a;
        for (int i = 0; i < 63; i++) {
            if ((b & (1LL << i)) != 0) {
                p *= q;
                p %= m;
            }
            q *= q;
            q %= m;
        }
        return p;
    }

    //逆元
    long long Div(long long a, long long b, long long m) {
        return (a * modpow(b, m - 2, m)) % m;
    }

    //点と点の距離を返す
    long double Dis(ll ax, ll ay, ll bx, ll by) {
        return sqrt(pow(ax - bx, 2) + pow(ay - by, 2));
    }

    //二つのベクトルから平行四辺形の面積を返す
    ll he(ll x0, ll y0, ll x1, ll y1, ll x2, ll y2) {//外積を二で割る
        return abs((x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0));
    }
    //



    template<typename T>
    ll Lis_size(V<T> arr, ll sz) {
        const T TINF = numeric_limits<T>::max();
        V<T> DP(sz + 1, TINF);
        DP[0] = -TINF;
        rep(i, 0, sz) {
            *lower_bound(all(DP), arr[i]) = arr[i];
        }
        ll ans = 0LL;
        rep(i, 1, sz + 1) {
            if (DP[i] != TINF)ans = i;
        }
        return ans;
    }

    string toBinary(ll n) {
        string r;
        while (n != 0LL) {
            r += (n % 2LL == 0LL ? "0" : "1");
            n /= 2LL;
        }
        return r;
    }

    template<typename T>
    V<ll> press(V<T> arr) {
        V<T> X = arr;
        sort(all(X));
        X.erase(unique(all(X)), X.end());
        V<ll> ans(arr.size());
        rep(i, 0LL, (ll)arr.size()) {
            ans[i] = lower_bound(all(X), arr[i]) - X.begin();
        }
        return ans;
    }

    P<V<V<ll>>, V<V<P<ll, ll>>>> warshall_floyd(ll N, V<V<P<ll, ll>>> G) {
        V<V<ll>> DP(N, V<ll>(N, INF));
        rep(i, 0, N)DP[i][i] = 0LL;
        V<V<P<ll, ll>>> prev(N, V<P<ll, ll>>(N, { INF,INF }));
        rep(i, 0, N) {
            reph(j, G[i]) {
                DP[i][j.FI] = j.SE;
                prev[i][j.FI] = { i,j.FI };
            }
        }
        rep(k, 0, N) {
            rep(i, 0, N) {
                rep(j, 0, N) {
                    if (chmin(DP[i][j], DP[i][k] + DP[k][j])) {
                        prev[i][j] = prev[k][j];
                    }
                }
            }
        }
        return { DP,prev };
    }

    template<typename T>
    void to_sum(V<T>& arr) {
        rep(i, 0, (ll)arr.size() - 1LL) {
            arr[i + 1] += arr[i];
        }
        return;
    }

    template<typename T>
    void including_map(ll H, ll W, V<V<T>>& G, T c) {
        V<V<T>> new_G(H + 2, V<T>(W + 2));
        rep(i, 0, W + 2)new_G[0][i] = c;
        rep(i, 1, H + 1) {
            new_G[i][0] = c;
            new_G[i][W + 1] = c;
            rep(j, 1, W + 1) {
                new_G[i][j] = G[i - 1][j - 1];
            }
        }
        rep(i, 0, W + 2)new_G[H + 1][i] = c;
        G = new_G;
        return;
    }
    
    template<typename T> class BIT {
private:
	int n;
	vector<T> bit;
public:
	// 0_indexed で i 番目の要素に x を加える
	void add(int i, T x){
		i++;
		while(i < n){
			bit[i] += x, i += i & -i;
		}
	}
	// 0_indexed で [0,i] の要素の和(両閉区間！！)
	T sum(int i){
		i++;
		T s = 0;
		while(i > 0){
			s += bit[i], i -= i & -i;
		}
		return s;
	}
	BIT(){}
	//初期値がすべて0の場合
	BIT(int sz) : n(sz+1), bit(n, 0){}
	BIT(const vector<T>& v) : n((int)v.size()+1), bit(n, 0){
		for(int i = 0; i < n-1; i++){
			add(i,v[i]);
		}
	}
	void print(){
		for(int i = 0; i < n-1; i++){
			cout << sum(i) - sum(i-1) << " ";
		}
		cout << "\n";
	}
	//-1スタート
	void print_sum(){
		for(int i = 0; i < n; i++){
			cout << sum(i-1) << " ";
		}
		cout << "\n";
	}
};
 
// u を昇順にソートするのに必要な交換回数(転倒数) (u は {0,..., n-1} からなる重複を許した長さ n の数列)
long long inv_count(const vector<long long>& u)
{
	int n = (int)u.size();
	BIT<long long> bt(n);
	long long ans = 0;
	for(int i = 0; i < n; i++){
		ans += i - bt.sum(u[i]);
		bt.add(u[i], 1);
	}
	return ans;
}

    set<ll> factor(ll N) {
        set<ll> ans;
        for (ll i = 1LL; i * i <= N; i++) {
            if (N % i)continue;
            ans.INS(i);
            ans.INS(N / i);
        }
        return ans;
    }

    V<ll> dijkstra(ll sz, V<V<P<ll, ll>>> G, ll s) {
        V<ll> ans(sz, INF); ans[s] = 0LL;
        priority_queue<P<ll, ll>, vector<P<ll, ll>>, greater<P<ll, ll>>> examine;
        examine.push({ 0LL,s });
        while (examine.size()) {
            P<ll, ll> p = examine.top();
            examine.pop();
            ll now = p.SE, dist = p.FI;
            if (ans[now] < dist)continue;
            reph(i, G[now]) {
                ll next = i.FI, c = i.SE;
                if (chmin(ans[next], dist + c)) {
                    examine.push({ dist + c,next });
                }
            }
        }
        return ans;
    }

    V<ll> pass(const V<V<ll>>& G, ll s, ll t) {
        V<ll> ans, res;
        function<void(ll,ll)> dfs = [&](ll now,ll p) {
            res.PB(now);
            if (now == t) {
                ans = res;
            }
            reph(next, G[now]) {
                if (next==p)continue;
                dfs(next,now);
            }
            res.pop_back();
            return;
        };
        dfs(s,-1);
        return ans;
    }

    // 負の数にも対応した mod (a = -11 とかでも OK)
    inline long long mod(long long a, long long m) {
        long long res = a % m;
        if (res < 0) res += m;
        return res;
    }

    // 拡張 Euclid の互除法
    long long extGCD(long long a, long long b, long long& p, long long& q) {
        if (b == 0) { p = 1; q = 0; return a; }
        long long d = extGCD(b, a % b, q, p);
        q -= a / b * p;
        return d;
    }
    long long extGcd(long long a, long long b, long long& p, long long& q) {
        if (b == 0) { p = 1; q = 0; return a; }
        long long d = extGcd(b, a % b, q, p);
        q -= a / b * p;
        return d;
    }
    // 逆元計算 (ここでは a と m が互いに素であることが必要)
    long long modinv(long long a, long long m) {
        long long x, y;
        extGCD(a, m, x, y);
        return mod(x, m); // 気持ち的には x % m だが、x が負かもしれないので
    }

    // Garner のアルゴリズム, x%MOD, LCM%MOD を求める (m は互いに素でなければならない)
    // for each step, we solve "coeffs[k] * t[k] + constants[k] = b[k] (mod. m[k])"
    //      coeffs[k] = m[0]m[1]...m[k-1]
    //      constants[k] = t[0] + t[1]m[0] + ... + t[k-1]m[0]m[1]...m[k-2]
    long long Garner(vector<long long> b, vector<long long> m, long long Mmod) {
        m.push_back(Mmod); // banpei
        vector<long long> coeffs((int)m.size(), 1);
        vector<long long> constants((int)m.size(), 0);
        for (int k = 0; k < (int)b.size(); ++k) {
            long long t = mod((b[k] - constants[k]) * modinv(coeffs[k], m[k]), m[k]);
            for (int i = k + 1; i < (int)m.size(); ++i) {
                (constants[i] += t * coeffs[i]) %= m[i];
                (coeffs[i] *= m[k]) %= m[i];
            }
        }
        return constants.back();
    }
    pair<long long, long long> ChineseRem(const vector<long long>& b, const vector<long long>& m) {
        long long r = 0, M = 1;
        for (int i = 0; i < (int)b.size(); ++i) {
            long long p, q;
            long long d = extGcd(M, m[i], p, q); // p is inv of M/d (mod. m[i]/d)
            if ((b[i] - r) % d != 0) return make_pair(0, -1);
            long long tmp = (b[i] - r) / d * p % (m[i] / d);
            r += M * tmp;
            M *= m[i] / d;
        }
        return make_pair(mod(r, M), M);
    }

    map<ll, ll> bunkai(ll n) {
        map<ll, ll> ans;
        ll Nn = n;
        for (int i = 2; i * i <= Nn; i++) {
            while (n % i == 0) {
                n /= i;
                ans[i]++;
            }
        }
        if (n > 1) { ans[n]++; }
        return ans;
    }

    template<typename T>
    void RLE(vector<T>& arr) {
        vector<T> res;
        res.push_back(arr[0]);
        for (const T t : arr) {
            if (res.back() != t)res.push_back(t);
        }
        arr = res;
        return;
    }

    vector<pair<long long, long long>> EulerTour(const vector<vector<long long>>& G) {
        long long N = (long long)G.size();
        vector<pair<long long, long long>> res(N);
        long long now = 0ll;
        function<void(long long, long long)> dfs = [&](long long v, long long p) {
            res[v].first = now;
            ++now;
            for (const long long next : G[v]) {
                if (next == p)continue;
                dfs(next, v);
            }
            res[v].second = now;
            ++now;
            return;
        };
        dfs(0, -1ll);
        return res;
    }
    
    template <typename T>
    struct BIT2D {
        int H, W;
        vector<vector<T>> bit;  // データの格納先
        BIT2D(int H_, int W_) { init(H_, W_); }
        void init(int H_, int W_) {
            H = H_ + 1;
            W = W_ + 1;
            bit.assign(H, vector<T>(W, 0));
        }
        void add(int h, int w, T x) {
            for (int i = h; i < H; i += (i & -i)) {
                for (int j = w; j < W; j += (j & -j)) {
                    bit[i][j] += x;
                }
            }
        }
        // 1≦i≦h かつ 1≦j≦w
        T sum(int h, int w) {
            T s(0);
            for (int i = h; i > 0; i -= (i & -i)) {
                for (int j = w; j > 0; j -= (j & -j)) {
                    s += bit[i][j];
                }
            }
            return s;
        }
        // h1≦i<h2 かつ w1≦j<w2
        T query(int h1, int w1, int h2, int w2) {
            return sum(h2 - 1, w2 - 1) - sum(h2 - 1, w1 - 1) - sum(h1 - 1, w2 - 1) + sum(h1 - 1, w1 - 1);
        }
    };
}

namespace Guest {
    const int MAX_VAL = 300000;
    int a[MAX_VAL]; //要素
    int cnt[MAX_VAL]; //区間内のiの個数
    int res;        //区間内の種類の数

    class Mo {
    private:
        vector<int> left, right;
        const int width;
        void add(const int id);
        void del(const int id);

    public:
        vector<int> ans;

        Mo(const int n) : width((int)sqrt(n)) {}
        //クエリ[l,r)
        void insert(const int l, const int r) {
            left.push_back(l), right.push_back(r);
        }
        void solve() {
            const int sz = (int)left.size();
            int nl = 0, nr = 0;
            vector<int> ord(sz);
            iota(ord.begin(), ord.end(), 0);
            sort(ord.begin(), ord.end(), [&](const int a, const int b) {
                const int c = left[a] / width, d = left[b] / width;
            return (c == d) ? ((c & 1) ? (right[b] < right[a]) : (right[a] < right[b])) : (c < d);
                });
            ans.resize(sz);
            for (const int id : ord) {
                while (nl > left[id]) add(--nl);
                while (nr < right[id]) add(nr++);
                while (nl < left[id]) del(nl++);
                while (nr > right[id]) del(--nr);
                ans[id] = res;
            }
        }
    };

    //idは元の配列のインデックス
    void Mo::add(const int id)
    {
        res -= cnt[a[id]] / 2;
        res += (++cnt[a[id]]) / 2;
    }

    void Mo::del(const int id)
    {
        res -= cnt[a[id]] / 2;
        res += (--cnt[a[id]]) / 2;
    }
    
    constexpr long long mod=MOD;
    class mint {
    long long x;
    public:
        mint(long long x=0) : x((x%mod+mod)%mod) {}
        mint operator-() const { 
          return mint(-x);
        }
        mint& operator+=(const mint& a) {
            if ((x += a.x) >= mod) x -= mod;
            return *this;
        }
        mint& operator-=(const mint& a) {
            if ((x += mod-a.x) >= mod) x -= mod;
            return *this;
        }
        mint& operator*=(const  mint& a) {
            (x *= a.x) %= mod;
            return *this;
        }
        mint operator+(const mint& a) const {
            mint res(*this);
            return res+=a;
        }
        mint operator-(const mint& a) const {
            mint res(*this);
            return res-=a;
        }
        mint operator*(const mint& a) const {
            mint res(*this);
            return res*=a;
        }
        mint pow(ll t) const {
            if (!t) return 1;
            mint a = pow(t>>1);
            a *= a;
            if (t&1) a *= *this;
            return a;
        }
        // for prime mod
        mint inv() const {
            return pow(mod-2);
        }
        mint& operator/=(const mint& a) {
            return (*this) *= a.inv();
        }
        mint operator/(const mint& a) const {
            mint res(*this);
            return res/=a;
        }           

        friend ostream& operator<<(ostream& os, const mint& m){
            os << m.x;
            return os;
        }
};
}

//
long long gcd(long long a, long long b) {
    if (b == 0LL)return a;
    return gcd(b, a % b);
}
long long lcm(long long a, long long b) {
    return a * b / gcd(a, b);
}

signed main() {
    /*
    文章を読み落としていませんか?
    制約も隅々まで読んでいますか?

    注意
    ・セグ木のupdate関数はl,rの値を渡したときにl以上r未満の区間だからご注意を
    　rは含みません
    ・BITって1-indexedなんだぜ
    　イケてるよな
    ・using namespace Warabi??
    */

    //using namespace Warabi;
    //mintのMODは確認した?
    in(N);in(M);in(L);--L;
    invll(T,N);ing_cost(G,N,M);
    V<V<ll>> dist(N);rep(i,0,N)dist[i]=Warabi::dijkstra(N,G,i);
    ll ans=INF;
    rep(to,0,N){
        //集める頂点=to
        ll res=0ll;
        rep(i,0,N)res+=dist[to][i]*T[i]*2;
        ll extra=dist[to][L];
        rep(i,0,N){
            //toに向かう途中でトラックによる
            if(T[i])chmin(extra,dist[L][i]-dist[i][to]);
        }
        chmin(ans,res+extra);
    }
    out(ans);
}