CF 965 C. Perform Operations to Maximize Score
原题链接：Problem - C - Codeforces
题意：多测，每次给出n和k，n代表长度为n的数组，每个数有二个属性，第一个是本身的值，第二个是这个数是否能被修改，如果能被修改那么就可以让k减去1让数的值增加1，可以从数组里面随意拿出一个数，对于剩下的数求出中位数，问拿出来的数和中位数的和的最大值是多少？
思路：贪心+二分，可以观察到最终的答案构成是拿出的数和中位数组成的，那么就只有二种情况，第一种是让拿出来的数变大，第二种是让中位数变大，不存在都变大的情况，因为花费1代价不一定可以让中位数变大，但是一定可以让拿出来的数变大。
第一种情况，就是当数可以被改变的时候，就去让这个数最大，并且拿出去，然后加上中位数就可以了。可以观察到，如果n是奇数，那么那中位数前面的数，不会改变中位数，拿中位数及其后面的数，会让中位数往前推一个。如果n是偶数，那么那中位数及其前面的数，会让中位数往后推一个，拿中位数及其后面的数，不会改变中位数。
第二种情况，直接将最大的数拿走，然后二分的求出中位数即可。因为如果要改变中位数，假定k无穷，并且所有的数都可以被改变，那么一定会用k来增加中位数及其之后的数，这些数最后一定是相等的，如果不将最大值拿走，那么到达相等的阶段要花费更多的代价。
最后二种答案取最值。
//冷静，冷静，冷静
//调不出来就重构
//#pragma GCC optimize(2)
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const int N=1e6+10,mod=1000000007;
struct node
{ll a,b;
}p[N];
bool cmp(node &a,node &b)
{return a.a<b.a;
}
ll n;
bool is(ll x,ll k)
{ll sum=0;for(int i=n-2;i>=0;i--){if(p[i].a>=x)sum++;else {if(p[i].a+k>=x&&p[i].b){sum++;k=k-(x-p[i].a);}else sum--;}}return sum>0;
}
ll solve(ll k)
{ll l=0,r=1e9+10;while(l+1<r){ll mid=l+r>>1;if(is(mid,k))l=mid;else r=mid;}if(is(r,k))l=r;return l;
}
void Jiuyuan()
{ll k;cin>>n>>k;for(int i=0;i<n;i++)cin>>p[i].a;for(int i=0;i<n;i++)cin>>p[i].b;ll ans=0;sort(p,p+n,cmp);for(int i=0;i<n;i++){if(p[i].b){if(n&1){if(i<(n-1)/2)ans=max(ans,p[i].a+k+p[(n-1)/2].a);else ans=max(ans,p[i].a+k+p[(n-1)/2-1].a);}else{if(i>(n-1)/2)ans=max(ans,p[i].a+k+p[(n-1)/2].a);else ans=max(ans,p[i].a+k+p[(n-1)/2+1].a);}}}ans=max(ans,solve(k)+p[n-1].a);cout<<ans<<endl;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll T=1;cin>>T;while(T--){Jiuyuan();}return 0;
}