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;
}