AT_jsc2025_final_b CatCoder Knapsack Contest

$ 4097 $ 年の CatCoder では、CatCoder Knapsack Contest（以下、CKC と略します）を開催することになりました。 各問題案にはそれぞれ難しさと面白さの $ 2 $ つのパラメータが $ 1,2 $ の $ 2 $ 段階で割り振られており、難しさが $ i\ (i = 1,2) $ で面白さが $ j\ (j = 1,2) $ である問題案は $ A_{i,j} $ 個あります。 CKC を $ 1 $ 回開催するためには、難しさの和と面白さの和がそれぞれちょうど $ X,Y $ であるような問題案の集合を使用する必要があります。 各問題案は高々 $ 1 $ 回の CKC にしか使用出来ません。 CKC を最大で何回開催出来るかを求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる。 > $ X $ $ Y $ $ A_{1,1} $ $ A_{1,2} $ $ A_{2,1} $ $ A_{2,2} $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースについて、CKC を開催出来る回数としてありうる最大値を出力せよ。

### Sample Explanation 1 $ 1 $ つ目のテストケースについて、以下のように問題案を使用することにより、CKC を $ 2 $ 回開催出来ます。 難しさ, 面白さ : $ 1,1 $ $ 1,2 $ $ 2,1 $ $ 2,2 $ 第 $ 1 $ 回 $ 1 $ 問 $ 2 $ 問 $ 1 $ 問 $ 0 $ 問第 $ 2 $ 回 $ 0 $ 問 $ 1 $ 問 $ 0 $ 問 $ 2 $ 問 ### Constraints - $ 1 \le T \le 10^5 $ - $ 1 \le X,Y \le 10^9 $ - $ 0 \le A_{i,j} \le 10^9 $ - 入力される値は全て整数