配点: $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$ 人となる．
• $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$

出力

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

2
2 2
9 1

3

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

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

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

3
1 1
0 8
7 1

9

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