#include "koala.h"
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
int N, W;
tuple<int,int,int> dp[201];
int simulation(vector<int> cost, int l, int r) {
rep(i, W+1) dp[i] = make_tuple(0, 0, 0);
rep(i, N) {
assert(cost[i] > 0);
for (int j=W-cost[i]; j>=0; j--) {
dp[j+cost[i]] = max(dp[j+cost[i]], make_tuple(get<0>(dp[j])+(i+1), get<1>(dp[j])+1, get<2>(dp[j])-(l<=i+1&&i+1<=r)));
}
}
return -get<2>(dp[W]);
}
int perm[100];
void solve(int l, int r, vector<int> set) {
assert(r-l+1 == set.size());
assert(l<=r);
//cout<<"["<<l<<","<<r<<"] {";for(int x: set)cout<<x<<",";cout<<"}\n";
if (l == r) {
perm[set[0]] = l;
return;
}
pair<int, P> mp = make_pair(INF, P(-1, -1));
for (int outside=1; outside<=100; outside++) {
for (int k=2; k<=100; k++) {
if ((outside-1)*(N-(r-l+1)) + (k-1)*(r-l+1) > W) break;
vector<int> cost(N);
for (int i=1; i<=N; i++) {
if (l <= i && i <= r) cost[i-1] = k;
else cost[i-1] = outside;
}
int left = simulation(cost, l, r);
int right = (r-l+1)-left;
if (left==0||right==0)continue;
mp = min(mp, make_pair(abs(left-right), P(k, outside)));
if (mp._1 <= 1) break;
}
if (mp._1 <= 1) break;
}
int val = mp._2._1;
int outside = mp._2._2;
//cout<<"val="<<val<<", outside="<<outside<<": "<<mp._1<<"\n";
assert(val!=-1);
int B[100], R[100];
rep(i, N) B[i] = outside-1;
for (int i : set) B[i] = val-1;
playRound(B, R);
vector<int> left, right;
for (int i : set) {
if (R[i] >= val) right.pb(i);
else left.pb(i);
}
solve(l, l+left.size()-1, left);
solve(l+left.size(), r, right);
}
int solve2(int l, int r, vector<int> set) {
assert(r-l+1 == set.size());
assert(l<=r);
//cout<<"["<<l<<","<<r<<"] {";for(int x: set)cout<<x<<",";cout<<"}\n";
if (l == r) return set[0];
pair<int, P> mp = make_pair(INF, P(-1, -1));
for (int outside=1; outside<=100; outside++) {
for (int k=2; k<=100; k++) {
if ((outside-1)*(N-(r-l+1)) + (k-1)*(r-l+1) > W) break;
vector<int> cost(N);
for (int i=1; i<=N; i++) {
if (l <= i && i <= r) cost[i-1] = k;
else cost[i-1] = outside;
}
int right = simulation(cost, l, r);
int left = (r-l+1)-right;
if (right==0) continue;
mp = min(mp, make_pair(right, P(k, outside)));
if (mp._1 <= 1) break;
}
if (mp._1 <= 1) break;
}
int val = mp._2._1;
int outside = mp._2._2;
//cout<<"val="<<val<<", outside="<<outside<<": "<<mp._1<<"\n";
assert(val!=-1);
int B[100], R[100];
rep(i, N) B[i] = outside-1;
for (int i : set) B[i] = val-1;
playRound(B, R);
vector<int> left, right;
for (int i : set) {
if (R[i] >= val) right.pb(i);
else left.pb(i);
}
return solve2(l+left.size(), r, right);
}
int minValue(int N, int W) {
int B[N], R[N];
rep(i, N) B[i] = 0;
B[0] = 1;
playRound(B, R);
rep(i, N) if (R[i] <= B[i]) return i;
abort();
}
int maxValue(int NN, int WW) {
N = NN, W = WW;
vector<int> left, right;
vector<int> all;
rep(i, N) all.pb(i);
return solve2(1, N, all);
}
int cmp(int w) {
int B[N], R[N];
rep(i, N) B[i] = 0;
B[0] = w;
B[1] = w;
playRound(B, R);
if (R[0]>=w+1&&R[1]>=w+1) return -1;
if (R[0] >= w+1) return 0;
if (R[1] >= w+1) return 1;
return -2;
}
int greaterValue(int NN, int WW) {
N = NN, W = WW;
const vector<int> cand = {1, 2, 3, 4, 5, 7, 8};
int lo = 0, hi = cand.size()-1;
while (hi-lo >= 1) {
int mid = (lo+hi)/2;
int x = (2*mid<=W?cmp(cand[mid]):-2);
if (x>=0) return x;
if (x==-1) lo = mid+1;
if (x==-2) hi = mid-1;
}
int x = cmp(cand[hi]);
assert(x>=0);
return x;
}
void allValues(int NN, int WW, int *P) {
N = NN, W = WW;
vector<int> left, right;
rep(i, N) perm[i] = -1;
vector<int> all;
rep(i, N) all.pb(i);
solve(1, N, all);
rep(i, N) P[i] = perm[i];
}
