D - Digit Sum Replace 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点: 500 点

問題文

DDCC 20XX の予選には，N 人のプログラマーが参加する予定です．しかし，会場の都合上，本戦には 9 人までしか参加できません．

そこで，予選を何ラウンドかに分けて勝ち抜き方式で行うことにしました．これは，以下のルールに従って行われます．

  • 最初のラウンドには N 人全員が参加する．
  • あるラウンドに X \ (X \geq 10) 人が参加するとき，次のラウンドに勝ち残る人数を以下のように決定する．
    • X の十進表記において，ある連続する 2 桁を選び，それらをその和で置き換えて得られる数を勝ち残る人数とする．
      例えば，X = 2378 のとき，勝ち残る人数は 578 (2,3 を選んだ場合)，2108 (3,7 を選んだ場合)，2315 (7,8 を選んだ場合) 人のいずれかとなる．
      X = 100 のときは，どちらの 2 桁を選んだとしても勝ち残る人数は 10 人となる．
  • 勝ち残った人数が 9 人以下となったら，予選を終了する．

DDCC 20XX の運営リーダーであるりんごさんは，できるだけ多くの予選ラウンドを開催したいです．
最大で何ラウンドの予選を開催できるか求めてください．

ただし，参加者数 N は非常に多くなる場合があるので，2 つの整数列 d_1, \ldots, d_M，c_1, \ldots, c_M として与えられます．
これは，N が十進表記において c_1 + c_2 + \ldots + c_M 桁の数であり，その先頭の c_1 桁の数字がいずれも d_1，続く c_2 桁の数字がいずれも d_2，\ldots，最後の c_M 桁の数字がいずれも d_M であることを表します．

制約

  • 1 \leq M \leq 200000
  • 0 \leq d_i \leq 9
  • d_1 \neq 0
  • d_i \neq d_{i+1}
  • c_i \geq 1
  • 2 \leq c_1 + \ldots + c_M \leq 10^{15}

入力

入力は以下の形式で標準入力から与えられます. 

M
d_1 c_1
d_2 c_2
:
d_M c_M

出力

予選ラウンドの数の最大値を出力してください．

入力例 1

2
2 2
9 1

出力例 1

3

この場合，予選の最初のラウンドには N=229 人が参加します．大会の経過の一例として、次のパターンがありえます．

  • ラウンド 1 に 229 人が参加し，ラウンド 2 に 49 人が参加し，ラウンド 3 に 13 人が参加し，本戦に 4 人が進出する．

このとき，予選は 3 ラウンド行われ、これが実は最適であることが分かります。

入力例 2

3
1 1
0 8
7 1

出力例 2

9

この場合，最初のラウンドには 1000000007 人が参加します．

Score: 500 points

Problem Statement

N programmers are going to participate in the preliminary stage of DDCC 20XX. Due to the size of the venue, however, at most 9 contestants can participate in the finals.

The preliminary stage consists of several rounds, which will take place as follows:

  • All the N contestants will participate in the first round.
  • When X contestants participate in some round, the number of contestants advancing to the next round will be decided as follows:
    • The organizer will choose two consecutive digits in the decimal notation of X, and replace them with the sum of these digits. The number resulted will be the number of contestants advancing to the next round.
      For example, when X = 2378, the number of contestants advancing to the next round will be 578 (if 2 and 3 are chosen), 2108 (if 3 and 7 are chosen), or 2315 (if 7 and 8 are chosen).
      When X = 100, the number of contestants advancing to the next round will be 10, no matter which two digits are chosen.
  • The preliminary stage ends when 9 or fewer contestants remain.

Ringo, the chief organizer, wants to hold as many rounds as possible. Find the maximum possible number of rounds in the preliminary stage.

Since the number of contestants, N, can be enormous, it is given to you as two integer sequences d_1, \ldots, d_M and c_1, \ldots, c_M, which means the following: the decimal notation of N consists of c_1 + c_2 + \ldots + c_M digits, whose first c_1 digits are all d_1, the following c_2 digits are all d_2, \ldots, and the last c_M digits are all d_M.

Constraints

  • 1 \leq M \leq 200000
  • 0 \leq d_i \leq 9
  • d_1 \neq 0
  • d_i \neq d_{i+1}
  • c_i \geq 1
  • 2 \leq c_1 + \ldots + c_M \leq 10^{15}

Input

Input is given from Standard Input in the following format:

M
d_1 c_1
d_2 c_2
:
d_M c_M

Output

Print the maximum possible number of rounds in the preliminary stage.

Sample Input 1

2
2 2
9 1

Sample Output 1

3

In this case, N = 229 contestants will participate in the first round. One possible progression of the preliminary stage is as follows:

  • 229 contestants participate in Round 1, 49 contestants participate in Round 2, 13 contestants participate in Round 3, and 4 contestants advance to the finals.

Here, three rounds take place in the preliminary stage, which is the maximum possible number.

Sample Input 2

3
1 1
0 8
7 1

Sample Output 2

9

In this case, 1000000007 will participate in the first round.