問題一覧 > 通常問題

No.3241 Make Multiplication of 8

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 101
作問者 : AngrySadEight / テスター : 👑 p-adic 👑 ygussany
ProblemId : 12290 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-07-04 00:59:11

問題文

Bob の家の押し入れに，$N$ 種類のカードがあります．また，封筒が $10^{888}$ 枚あります．

$i$ 種類目のカードには整数 $A_i$ が書かれており，全部で $B_i$ 枚あります．

Bob は，次に示す操作を $0$ 回以上好きな回数行うことができます．

  • 操作：押し入れにあるカードを $1$ 枚以上，およびまだカードの入っていない封筒を $1$ 枚選ぶ．選んだカードを全て押し入れから取り出し，選んだ封筒に入れる．

Bob は，入っているカードに書かれた数の総積が $8$ の倍数となる封筒をできるだけ多く作りたいです．

カードが $1$ 枚以上入っている封筒であって，入っているカードに書かれた数の総積が $8$ の倍数となる封筒は最大でいくつ作れるか，求めてください．

制約

  • 入力は全て整数
  • $1 \leq N \leq 8.88 \times 10^4$
  • $1 \leq A_i \leq 8.88 \times 10^8$
  • $1 \leq B_i \leq 8.88 \times 10^8$

入力

入力は以下の形式で標準入力から与えられる．

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

出力

答えを出力せよ．

サンプル

サンプル1
入力
3
80 2
81 3
82 4
出力
3

次のように封筒にカードを入れることで，条件を満たす封筒を $3$ 個作ることができます．

  • 空の封筒に，$80$ が書かれたカードを $1$ 枚入れる．カードに書かれた数の総積は $80$ となり，これは $8$ の倍数なので条件を満たす．
  • 空の封筒に，$80$ が書かれたカードと，$81$ が書かれたカードを $1$ 枚ずつ入れる．カードに書かれた数の総積は $80 \times 81 = 6480$ となり，これは $8$ の倍数なので条件を満たす．
  • 空の封筒に，$81$ が書かれたカード $1$ 枚と，$82$ が書かれたカードを $3$ 枚入れる．カードに書かれた数の総積は $81 \times 82^3 = 44660808$ となり，これは $8$ の倍数なので条件を満たす．

どのようにしても，条件を満たす封筒を $4$ 個以上作ることはできません．

サンプル2
入力
8
888000000 888000000
887999999 887999999
887999998 887999998
887999997 887999997
887999996 887999996
887999995 887999995
887999994 887999994
887999993 887999993
出力
2071999994

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。