二分套三分，好！—— 石……

首先很显然我们需要二分不平衡度 $d$。$d$ 确定之后，$\max_a$ 和 $\min_b$ 所构成的区间大小显然也固定为 $d$。此时我们需要找到在此区间大小下操作次数最少的区间，然后我们惊奇地发现我们可以三分这个区间！这个问题可以类比为货仓选址，显然区间越靠近中间的位置，所花费的代价（操作次数）就越小。

而对于确定的 $\max_a$ 和 $\min_b$ 所构成的区间，如何计算其代价呢？其实也很容易。我们依次考虑每一个谷仓，显然为了满足操作后 $a_i\leq\max_a$ 且 $b_i\geq\min_b$：

• 如果 $a_i > \max_a$，我们至少需要卖出 $a_i-\max_a$ 捆干草；
• 如果 $b_i < \min_b$，我们至少需要买进 $\min_b-b_i$ 袋饲料；
• 而题目中又给出了一个美妙的条件：“他选择一个谷仓 $i$，卖出它的一捆干草，并为同一个谷仓购买一袋新饲料。”这说明这些转移都是独立的，可以单独考虑。
• 更好的是，FJ 还是个土豪：“他的农场中允许出现负数（他不害怕负债）。”这意味着我们为了满足上述的两个条件，可以任意地卖出干草和买进饲料，因为题目并没有对 $\min_a$ 与 $max_b$ 做出限制。

那么第 $i$ 个谷仓所产生的贡献是 $\max(a_i-\max_a,\min_b-b_i,0)$，完了。

细节较多，不然也不会有上面那张头图。

上代码：

#include<bits/stdc++.h>
#pragma GCC optimize(3)
#pragma GCC optimize(2)
#define int  __int128//没错，以下代码会爆long long
#define ll  long long
using namespace std;
ll t,n,k,a[50005],b[50005];
inline int check(ll na,ll d){
	int sum=0;
	for(int i=1;i<=n;i++){
		sum+=max({0ll,a[i]-na,na-d-b[i]});//计算代价
	}
	return sum;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--){
		cin>>n>>k;
		ll maxa=0,minb=1e18;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			maxa=max(maxa,a[i]);
		}
		for(int i=1;i<=n;i++){
			cin>>b[i];
			minb=min(minb,b[i]);
		}
		ll ld=maxa-minb-2*k,rd=maxa-minb;
		ll ans=-1;
		while(ld<=rd){//二分不平衡度
			ll mid=(ld+rd)/2;
			ll la=maxa-k,ra=maxa;
			int mink=9e30;
			while(ra-la>=3){//三分找操作次数最小区间
				int lmid=la+(ra-la)/3,rmid=ra-(ra-la)/3;
				if(check(lmid,mid)<check(rmid,mid))ra=rmid;
				else la=lmid;
			}
			for(int i=la;i<=ra;i++)mink=min(mink,check(i,mid));
			if(mink<=k)rd=mid-1,ans=mid;
			else ld=mid+1;
		}
		cout<<ans<<"\n";
	}
}

另：USACO 的老年机一开始竟然没跑过，需要卡常……

再另：本题解写于乙巳蛇年腊月二十五，祝审核此题解的管理员，以及所有看到此题解的谷民们新年快乐！