#include #define MAXN 1000010 using namespace std; long long n, b; struct stick { long long h, p, i; bool operator< (stick other) { double f = (double)p / (double)h; double s = (double)other.p / (double)other.h; return f > s; } }arr[MAXN]; long long ans[MAXN], cur = 1e18, k, penalty, knum, activeNum, activeLength[MAXN]; unsigned long long dif; bool solution1 = false; vector sz, szs; vector podredba[MAXN]; mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count()); std::chrono::high_resolution_clock::time_point beginOfTime; long long rnd(int i) { return mt() % i; } void read() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); freopen("sticks.in", "r", stdin); freopen("sticks.out", "w", stdout); cin>>n>>b; for(int i = 0; i < n; i ++) { cin>>arr[i].h; arr[i].i = i; } for(int i = 0; i < n; i ++) { cin>>arr[i].p; } } void solve(long long ttt) { while(1) { auto bb = chrono::high_resolution_clock::now(); if(chrono::duration_cast(bb - beginOfTime).count() > ttt) break; int l = 0, done = 0; k = 0; penalty = 0; szs.clear(); while(done < n) { int csz = 0; while(done < n && l + arr[done].h <= b) { l += arr[done].h; done ++; csz ++; } if(done < n && arr[done].p < dif && l != b) { l += arr[done].h; done ++; csz ++; } szs.push_back(csz); if(l > b) { penalty += arr[done - 1].p; } k ++; l = 0; } if(k * k * k + penalty < cur) { cur = k * k * k + penalty; for(int i = 0; i < n; i ++) { ans[i] = arr[i].i; } knum = k; sz = vector(szs); } random_shuffle(arr, arr + n, rnd); } } void proba() { sort(arr, arr + n); activeNum = 0; int last = 0; for(int i = 0; i < n; i ++) { bool done = false; if(n - i <= activeNum) { last = i; break; } for(int j = 0; j <= activeNum; j ++) { if(activeLength[j] + arr[i].h < b) { activeLength[j] += arr[i].h; podredba[j].push_back(arr[i].i + 1); done = true; break; } } if(done == false) { activeLength[++activeNum] = arr[i].h; podredba[activeNum].push_back(arr[i].i + 1); if(arr[i].h > b) penalty += arr[i].p; } } for(int i = last; i < n; i ++) { bool done = false; for(int j = 0; j <= activeNum; j ++) { if(activeLength[j] < b) { activeLength[j] += arr[i].h; podredba[j].push_back(arr[i].i + 1); if(arr[i].h > b) penalty += arr[i].p; done = true; break; } } if(done == false) { activeLength[++activeNum] = arr[i].h; podredba[activeNum].push_back(arr[i].i + 1); if(arr[i].h > b) penalty += arr[i].p; } } } void print1() { cout< 100000) ttttt = 4000; else if(n > 10000) ttttt = 4300; else ttttt = 4600; beginOfTime = chrono::high_resolution_clock::now(); if(n < 600000)proba(); solve(ttttt); if(activeNum * activeNum * activeNum + penalty <= cur && n < 500000) { print1(); } else { cout<