問題一覧 > 通常問題

No.3241 Make Multiplication of 8

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 104
作問者 : 👑 AngrySadEight / テスター : 👑 p-adic ygussany
お気に入りにしたユーザー ProblemId : 12290 / 自分の提出
問題文最終更新日: 2025-07-04 00:59:11
Make Multiplication of 8
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Show the original
yukicoder contest 479 AngrySadEightお誕生日コンテスト2025 (順位表) の他の問題:

Problem Statement

In the closet of Bob's house, there are $N$ types of cards. There are also $10^{888}$ envelopes.

Each card of the $i$-th type has the integer $A_i$ written on it, and there are $B_i$ such cards in total.

Bob can perform the following operation any number of times, $0$ or more.

  • Operation: Choose $1$ or more cards in the closet and $1$ envelope that does not yet contain any cards. Take all the chosen cards out of the closet and put them into the chosen envelope.

Bob wants to make as many envelopes as possible such that the product of the numbers written on the cards inside is a multiple of $8$.

Find the maximum number of envelopes that can be made such that the envelope contains $1$ or more cards and the product of the numbers written on the cards inside is a multiple of $8$.

Constraints

  • All inputs are integers
  • $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$

Input

The input is given from standard input in the following format.

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

Output

Print the answer.

Sample

Sample 1
Input
3
80 2
81 3
82 4
Output
3

By putting cards into envelopes as follows, you can make $3$ envelopes satisfying the condition.

  • Put $1$ card with $80$ written on it into an empty envelope. The product of the numbers written on the cards is $80$, which is a multiple of $8$, so the condition is satisfied.
  • Put a card with $80$ written on it and a card with $81$ written on it, $1$ card each, into an empty envelope. The product of the numbers written on the cards is $80 \times 81 = 6480$, which is a multiple of $8$, so the condition is satisfied.
  • Put $1$ card with $81$ written on it and $3$ cards with $82$ written on them into an empty envelope. The product of the numbers written on the cards is $81 \times 82^3 = 44660808$, which is a multiple of $8$, so the condition is satisfied.

No matter what you do, you cannot make $4$ or more envelopes satisfying the condition.

Sample 2
Input
8
888000000 888000000
887999999 887999999
887999998 887999998
887999997 887999997
887999996 887999996
887999995 887999995
887999994 887999994
887999993 887999993
Output
2071999994

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