Full Solution: We will start by binary searching on the answer. In particular, we'll see if it is possible to attain $\max(a) - \min(b) \le Y$.

As a preprocessing step, we need to handle pairs that start out with $a_i - b_i > Y$.

Let's define $f(x)$ to be the number of transfers to make such that $\min(b) = x$, and look at how $f$ changes as we increase $x$ from $\min(b)$ to infinity. We define $f_i(x)$ to be the cost of making the pair $(a_i, b_i)$ compliant with $\min(b) \ge x$ and $\max(a) \le x + Y$, so $f(x) = \displaystyle\sum_{i} f_i(x)$.

Informally, if we think about how $f_i(x)$ changes, we know that as $x$ goes to infinity, $f_i(x)$ also increases to infinity. For some pairs, $f_i(x)$ is constant and then increases to infinity. For other pairs, we observe that $f_i(x)$ decreases, then stays constant, then increases. This gives us reason to make the following claim: $f(x+1) - f(x)$ is nondecreasing as $x$ increases. We will now proceed to prove this.

We will start by showing that $f_i(x)=\max(a_i - (x + Y), 0, x - b_i)$. There are three constraints that are relevant: in order, we have to make sure $a_i \le x+Y$, the number of transfers must be nonnegative, and we have to make sure $b_i \ge x$.

Note that at the transitions when the function that is maximal for a given $x$ changes, we must change from a function with a smaller leading coefficient of $x$ to a larger leading coefficient of $x$. This shows that $f_i(x+1) - f_i(x)$ is nondecreasing as $x$ increases. This property therefore holds as well for $f(x+1) - f(x)$.

Therefore, we can track all values $x$ where $f(x+1) - f(x)$ increases and evaluate $f(x)$ exactly when $f(x+1) - f(x)$ goes from being negative to zero. If, at this point $f(x) \le K$, then it is possible. Otherwise, it is impossible.

In my code below, I sort all the values where this quantity increases and maintain a running sum. The time complexity is $O(N\log N\log 10^{18})$.

It is possible to remove a log factor from this solution by querying for the exact value where $f(x+1) - f(x)$ goes to zero using $\texttt{std::nth_element}$, but this was not necessary to pass.

Less efficient solutions, such as evaluating $f(x)$ at all slope change points rather than only one, could still pass the first two subtasks.

My C++ code:

#include <algorithm>
#include <array>
#include <iomanip>
#include <iostream>
#include <vector>

using namespace std;

void solve() {
  int n;
  int64_t k;
  cin >> n >> k;
  vector<int64_t> a(n), b(n);
  for(auto& x: a) cin >> x;
  for(auto& x: b) cin >> x;
  auto can = [&](int64_t thresh) -> bool {
    vector<int64_t> na = a, nb = b;
    int64_t have = k;
    for(int i = 0; i < n; i++) {
      if(na[i] - nb[i] > thresh) {
        int64_t use = (na[i] - nb[i] - thresh + 1) / 2;
        if(use > have) return false;
        na[i] -= use;
        nb[i] += use;
        have -= use;
      }
    }
    if(have < 0) return false;
    int64_t lhs = *min_element(nb.begin(), nb.end());
    int64_t abound = lhs + thresh;
    __int128_t need = 0;
    vector<int64_t> xincs;
    int64_t lastx = lhs;
    int64_t inc = 0;
    for(int i = 0; i < n; i++) {
      xincs.push_back(nb[i]);
      if(na[i] > abound) {
        need += na[i] - abound;
        inc--;
        xincs.push_back(na[i]-thresh);
      }
    }
    if(need <= have) return true;
    sort(xincs.begin(), xincs.end());
    for(int i = 0; i < xincs.size() && inc < 0; i++) {
      auto currx = xincs[i];
      need += (currx - lastx) * __int128_t(inc);
      if(need <= have) return true;
      inc++;
      lastx = currx;
    }
    return false;
  };
  int64_t lhs = -2.1e18;
  int64_t rhs = 2.1e18;
  while(lhs < rhs) {
    int64_t mid = lhs + (rhs - lhs) / 2;
    if(can(mid)) rhs = mid;
    else lhs = mid + 1;
  }
  cout << lhs << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  while(t--) solve();
}