Loading...

C - Eat 4x

Ceylon

1024

300

点

問題文

$T$ 個のテストケースについて、以下の問題を解いてください。

問題

カードの山があります。それぞれのカードには非負整数が $1$ つ書かれています。山にあるカードに書かれた非負整数は全部で $N$ 種類で、非負整数 $A_{i}$ が書かれたカードは $B_{i}$ 枚あります。このとき、次の操作を最大で何回行えるでしょうか。

カードの山から、書かれた非負整数の和が $4$ の倍数になるように $1$ 枚以上のカードを選んで印をつける。そして、印をつけたすべてのカードを食べる。

制約

入力はすべて整数
$1 \le T \le 2 \times 10^{5}$
$1 \le N \le 2 \times 10^{5}$
$0 \le A_{i} \le 10^{9}$
$1 \le B_{i} \le 10^{12}$
$A_{i} \neq A_{j} (i \neq j)$
$1$ つの入力に含まれるテストケースについて、それらの $N$ の総和は $2 \times 10^{5}$ を超えない

入力

入力は標準入力から与えられる。入力の $1$ 行目は以下の形式である。

$T$

その後、 $T$ 個のテストケースが続く。各テストケースは以下の形式で与えられる。

$N$
$A_{1}$ $A_{2}$ $\ldots$ $A_{N}$
$B_{1}$ $B_{2}$ $\ldots$ $B_{N}$

出力

$T$ 行出力せよ。
$i (1 \le i \le T)$ 行目には、 $i$ 番目に入力されたテストケースに対する答えを出力せよ。

入力例 1

3
5
1 2 6 4 7
1 1 1 2 1
2
0 1
100 100
10
1 5 35 9 100 29 83 62 92834 233
30000000000 129832322130 39324933422 923 102930291 842981394 9439249833 287218322 92753024 999821738

出力例 1

4
125
77284834951

$1$ 番目のテストケースでは、食べるカードを $(4) \rightarrow (4) \rightarrow (2,6) \rightarrow (1,7)$ のようにすることで $4$ 回の操作を行うことができます。操作を $5$ 回以上行うことはできないため、これは最適な操作の一例です。
$2$ 番目のテストケースでは、例えば $0$ が書かれたカードを $1$ 枚ずつ食べたのちに $1$ が書かれたカードを $4$ 枚ずつまとめて食べることで、合計 $125$ 回の操作を行えます。
$3$ 番目のテストケースのように、入力や答えが $32$ bit整数に収まらないことがあるので注意してください。