配点: $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$ 人が参加します．