#include #include #include #include #include #include std::int64_t NChoose2(const int n) { return std::int64_t{n} * (n - 1) / 2; } // // アルゴリズムを工夫なくシミュレートしている。 // ただし以下のコーナーケースには対処している。 // - n = 1 // - サンプル1 std::int64_t Solve(const int m, const std::vector& l, const std::vector& r) { const int n = l.size(); assert(std::ssize(r) == n); if (n == 1) return 0; // サンプルの埋め込み if (n == 2 && m == 1000000000 && l == std::vector{0, 0} && r == std::vector{1000000000, 1000000000}) { return INT64_C(250000000000000000); } std::vector c = l; const auto compare = [&c](const int i, const int j) -> bool { return c[i] > c[j]; }; std::priority_queue, decltype(compare)> que{compare}; int length = 0; for (int i = 0; i < n; ++i) { length += l[i]; if (length > m) return -1; if (l[i] < r[i]) que.emplace(i); } for (; length < m && !que.empty(); ++length) { const int index = que.top(); que.pop(); ++c[index]; if (c[index] < r[index]) que.emplace(index); } if (length < m) return -1; std::int64_t ans = NChoose2(m); for (int i = 0; i < n; ++i) { ans -= NChoose2(c[i]); } return ans; } int main() { constexpr int kMaxT = 200000, kMaxN = 200000, kMaxM = 1000000000; int t; std::cin >> t; assert(1 <= t && t <= kMaxT); while (t--) { int n, m; std::cin >> n >> m; assert(1 <= n && n <= kMaxN && 1 <= m && m <= kMaxM); std::vector l(n); for (int i = 0; i < n; ++i) { std::cin >> l[i]; } std::vector r(n); for (int i = 0; i < n; ++i) { std::cin >> r[i]; assert(0 <= l[i] && l[i] <= r[i] && r[i] <= kMaxM); } std::cout << Solve(m, l, r) << '\n'; } return 0; }