int n, k, s = 0;
cin >> n >> k;
for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    s += x;
}
for (int ans = 0;; ans++) {
    int a = 2 * (s + ans * k);
    int b = (2 * k - 1) * (ans + n);

    if (a >= b) {
        cout << ans;
        return 0;
    }
}

for (int i = 0; i < n; i++) {
    cin >> k[i] >> l[i];
    a.push_back(make_pair(min(2 * k[i], l[i]) - min(k[i], l[i]), i));
}
sort(a.rbegin(), a.rend());

long long ans = 0;
for (int i = 0; i < f; i++) {
    int pos = a[i].second;
    ans += min(2 * k[pos], l[pos]);
}
for (int i = f; i < n; i++) {
    int pos = a[i].second;
    ans += min(k[pos], l[pos]);
}
cout << ans;

st[0] = 1;
for ( int j = 1; j < maxn; j++ )
    st[j] = ( 2 * st[j - 1] ) % base;
int n;
scanf ( "%d", &n );
for ( int j = 0; j < n; j++ )
    scanf ( "%d", &a[j] );
sort( a, a + n );
int ans = 0;
for ( int j = 1; j < n; j++ ) {
    int len = a[j] - a[j - 1];
    int cntL = j;
    int cntR = n - j;
    int add = ( 1LL * ( st[cntL] - 1 + base ) * ( st[cntR] - 1 + base ) ) % base;
    ans = ( 1LL * ans + 1LL * len * add ) % base;
}
printf ( "%d\n", ans );

int query(int x,int y){
    if(x==-1)return 0;
    cout<<1<<' '<<x<<' '<<y<<endl;
    string ret;
    cin>>ret;
    return ("TAK"==ret);
}

int get(int l,int r){
    if(l>r)return -1;

    while(l<r){
        int m=(l+r)/2;
        if(query(m,m+1)){
            r=m;
        }else l=m+1;
    }
    return l;
}

int main() {
    int n,k;
    cin>>n>>k;

    int x=get(1,n);
    int y=get(1,x-1);
    if(!query(y,x))y=get(x+1,n);
    cout<<2<<' '<<x<<' '<<y<<endl;

    return 0;
}

ll dp[32][2][2][2];
ll sum[32][2][2][2];

void add(ll &x,ll y){
    x+=y;
    if(x>=mod)x-=mod;
}

void sub(ll &x,ll y){
    x-=y;
    if(x<0)x+=mod;
}

ll mul(ll x,ll y){
    return x*y%mod;
}

ll pot[32];

ll solve(int x,int y,int z){
    if(x<0||y<0||z<0)return 0;
    memset(dp,0,sizeof dp);
    memset(sum,0,sizeof sum);
    vi A,B,C;
    rep(j,0,31){
        A.pb(x%2);x/=2;
        B.pb(y%2);y/=2;
        C.pb(z%2);z/=2;
    }
    reverse(all(A));
    reverse(all(B));
    reverse(all(C));
    dp[0][1][1][1]=1;
    sum[0][1][1][1]=0;
    rep(i,0,31){
        rep(a,0,2)rep(b,0,2)rep(c,0,2){
            rep(x,0,2)rep(y,0,2){
                int z=x^y;
                if(a==1&&A[i]==0&&x==1)continue;
                if(b==1&&B[i]==0&&y==1)continue;
                if(c==1&&C[i]==0&&z==1)continue;
                add(dp[i+1][a&(A[i]==x)][b&(B[i]==y)][c&(C[i]==z)],dp[i][a][b][c]);
                add(sum[i+1][a&(A[i]==x)][b&(B[i]==y)][c&(C[i]==z)],sum[i][a][b][c]);
                add(sum[i+1][a&(A[i]==x)][b&(B[i]==y)][c&(C[i]==z)],mul(z<<(30-i),dp[i][a][b][c]));

            }
        }
    }
    ll res=0;
    rep(a,0,2)rep(b,0,2)rep(c,0,2){
        add(res,sum[31][a][b][c]);
        add(res,dp[31][a][b][c]);
    }
    return res;
}

int main(){
    int T;
    cin>>T;
    while(T--){
        int x,y,x2,y2,k;
        cin>>x>>y>>x2>>y2>>k;
        --x;--y;--x2;--y2;--k;
        ll res=0;
        add(res,solve(x2,y2,k));
        sub(res,solve(x2,y-1,k));
        sub(res,solve(x-1,y2,k));
        add(res,solve(x-1,y-1,k));
        cout<<res<<'\n';
    }
    return 0;
}

struct node {
    int prior, sz, dp, add;
    node *l, *r;
    node ( int x ) {
        prior = ( rand() << 15 ) | rand();
        // sz = 1;
        dp = x;
        l = r = NULL;
        add = 0;
    }
};
 
typedef node * pnode;

void push( pnode T ) {
    T -> dp += T -> add;
    if ( T -> l )
        T -> l -> add += T -> add;
    if ( T -> r )
        T -> r -> add += T -> add;
    T -> add = 0;
}
 
void merge( pnode &T, pnode L, pnode R ) {
    if ( !L ) {
        T = R;
        return;
    }
    if ( !R ) {
        T = L;
        return;
    }
    if ( L -> prior > R -> prior ) {
        push( L );
        merge( L -> r, L -> r, R );
        T = L;
        return;
    }
    push( R );
    merge( R -> l, L, R -> l );
    T = R;
}
 
void split( pnode T, int value, pnode &L, pnode &R ) {
    if ( !T ) {
        L = R = NULL;
        return;
    }
    push( T );
    if ( T -> dp >= value ) {
        split( T -> l, value, L, T -> l );
        R = T;
        return;
    }
    split( T -> r, value, T -> r, R );
    L = T;
}
 
int findBegin( pnode T ) {
    push( T );
    if ( !T -> l )
        return T -> dp;
    return findBegin( T -> l );
}
 
int findMax( pnode T, int n ) {
    if ( !T )
        return 0;
    push( T );
    return findMax( T -> l, n ) + findMax( T -> r, n ) + ( T -> dp <= inf ? 1 : 0 );
}

pair < int, int > a[maxn];
pnode T = new node( 0 );
pnode L = NULL;
pnode M = NULL;
pnode R = NULL;
pnode rubbish = NULL;
 
void solve() {
    int n;
    scanf ( "%d", &n );
    for ( int j = 1; j <= n; j++ )
        scanf ( "%d%d", &a[j].f, &a[j].s );
    for ( int j = 1; j <= n; j++ )
        merge( T, T, new node( inf + j ) );
    for ( int j = 1; j <= n; j++ ) {
        split( T, a[j].f, L, R );
        split( R, a[j].s, M, R );
        if ( M )
            M -> add += 1;
        int cnt = findBegin( R );
        split( R, cnt + 1, rubbish, R );
        merge( T, L, new node( a[j].f ) );
        merge( T, T, M );
        merge( T, T, R );
    }
    printf ( "%d\n", findMax( T, n ) - 1 );
}

#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <numeric>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <vector>
#include <math.h>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>

using namespace std;

typedef long long ll;
typedef long double ld;

template <typename T>
T nextInt() {
    T x = 0, p = 1;
    char ch;
    do { ch = getchar(); } while(ch <= ' ');
    if (ch == '-') {
        p = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * p;
}
const int maxN = (int)2e5 + 10;
const int maxL = 17;
const int INF = (int)1e9;
const int mod = (int)1e9 + 7;
const ll LLINF = (ll)1e18 + 5;

int mul(int x, int y) {
    return 1LL * x * y % mod;
}

void add(int &x, int y) {
    x += y;
    if (x >= mod) x -= mod;
}

void sub(int &x, int y) {
    x -= y;
    if (x < 0) x += mod;
}

int n;
vector <int> g[maxN];
vector <int> d[maxN];
vector <int> coefs[maxN];
int phi[maxN];
int inv[maxN];
int a[maxN];

int tmp[maxN];

void productToTmp(int a, int b) {
    for (size_t it = 0; it < d[a].size(); it++) {
        for (size_t jt = 0; jt < d[b].size(); jt++) {
            int x = d[a][it];
            int cx = coefs[a][it];
            int y = d[b][jt];
            int cy = coefs[b][jt];
            add(tmp[x * y], mul(cx, cy));
        }
    }
}

void precalc() {
    inv[1] = 1;
    for (int i = 1; i < maxN; ++i) {
        phi[i] = i;
        if(i > 1) inv[i] = mul(mod - mod / i, inv[mod % i]);
    }
    for (int i = 1; i < maxN; ++i) {
        for (int j = i; j < maxN; j += i) {
            d[j].push_back(i);
            if (j != i) phi[j] -= phi[i];
        }
    }
    for (int i = 1; i < maxN; ++i) {
        coefs[i].resize(d[i].size());
    }
    coefs[1][0] = 1;
    for (int x = 2; x < maxN; x++) {
        if ((int)d[x].size() == 2) {
            coefs[x][0] = 1;
            coefs[x][1] = inv[x - 1];
        } else {
            int lp = d[x][1];
            int z = x;
            while (z % lp == 0) {
                z /= lp;
            }
            for (int y: d[x]) {
                tmp[y] = 0;
            }
            productToTmp(lp, z);
            for (size_t it = 0; it < d[x].size(); it++) {
                coefs[x][it] = tmp[d[x][it]];
            }
        }
    }
}

int nodes[maxN];
int len = 0;
int sz[maxN];
int blocked[maxN];
int level[maxN];
int anc[maxN];

void calc_sizes(int v, int p = -1) {
    nodes[len++] = v;
    sz[v] = 1;
    anc[v] = p;
    for (int x: g[v]){
        if (blocked[x] || x == p) continue;
        calc_sizes(x, v);
        sz[v] += sz[x];
    }
}

int sum_phi[maxN];

int list_len;
int list[maxN];
int depth[maxN];

void get_list(int v, int par = -1, int dpth = 1) {
    list[list_len] = v;
    depth[list_len++] = dpth;
    for (int x: g[v]) {
        if (par == x || blocked[x]) continue;
        get_list(x, v, dpth + 1);
    }
}

int sum[maxN];

int calc(int value) {
    int cur = 0;
    for(size_t i = 0; i < d[value].size(); ++i) {
        int x = d[value][i];
        add(cur, mul(sum_phi[x], coefs[value][i]));
    }
    return mul(cur, phi[value]);
}

int total = 0;

void solve(int root) { //root is a centroid
    for (int i = 0; i < len; ++i) {
        int u = nodes[i];
        int y = a[u];
        for (int x: d[y]) {
            add(sum_phi[x], phi[y]);
        }
    }
    for (int child: g[root]) {
        if (blocked[child]) continue;

        list_len = 0;
        get_list(child, root);
        {
            //excluding everything which can be counted twice
            for(int i = 0; i < list_len; ++i) {
                int u = list[i];
                int y = a[u];
                for(int x: d[y]) {
                    sub(sum_phi[x], phi[y]);
                }
            }
        }
        {
            for (int i = 0; i < list_len; ++i) {
                int u = list[i];
                int d = depth[i];
                int value = a[u];
                add(total, mul(d, calc(value)));
            }
        }
        {
            //including back
            for(int i = 0; i < list_len; ++i) {
                int u = list[i];
                int y = a[u];
                for(int x: d[y]) {
                    add(sum_phi[x], phi[y]);
                }
            }
        }
    }

    //clear
    for (int i = 0; i < len; ++i) {
        int u = nodes[i];
        int y = a[u];
        for (int x: d[y]) {
            sum_phi[x] = 0;
        }
    }
}

void build(int v, int lev) {
    len = 0;
    calc_sizes(v);
    int centroid = -1;
    for (int i = 0; i < len; ++i) {
        int u = nodes[i];
        int maxChildSize = len - sz[u];
        for (int x: g[u]) {
            if (x != anc[u] && !blocked[x]) {
                maxChildSize = max(maxChildSize, sz[x]);
            }
        }
        if (maxChildSize <= len / 2) {
            centroid = u;
        }
    }
    blocked[centroid] = true;
    level[centroid] = lev;
    solve(centroid);

    for (int x: g[centroid]) {
        if (blocked[x]) continue;
        build(x, lev + 1);
    }
}

int main() {

   // freopen("input.txt", "r", stdin);
   // freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(0);
    precalc();
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 1; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        --x; --y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    build(0, 0);

    total = mul(total, inv[n]);
    total = mul(total, inv[n - 1]);
    total = mul(total, 2);

    cout << total << endl;
    return 0;
}