#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; #define rep(i,k) for (int i = 0; i < (int)(k); i++) #define all(c) begin(c), end(c) int main() { cin.tie(0); ios::sync_with_stdio(0); int d; cin >> d; for (int i = 0; i < d; i++) { int a, b; cin >> a >> b; if (a > b) swap(a, b); int n; cin >> n; vector x(n); for (int i = 0; i < n; i++) { cin >> x[i]; } sort(x.begin(), x.end()); int lb = 0, ub = n + 1; while (lb + 1 < ub) { int mid = (ub + lb) / 2; auto can = [&](int k) { int s = accumulate(x.begin(), x.begin() + k, 0); vector dp(s + 1); dp[0] = true; for (int i = 0; i < k; ++i) { for (int j = s; j >= x[i]; --j) { dp[j] |= dp[j - x[i]]; } } for (int i = 0; i <= s; i++) { if (dp[i]) { int sa = i; int sb = s - i; if (sa > sb) swap(sa, sb); if (sa <= a && sb <= b) return true; } } return false; }; if (can(mid)) { lb = mid; } else { ub = mid; } } cout << lb << endl; } }