题目描述

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$ であることを表します．

输入格式

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

$M$ $d_1$ $c_1$ $d_2$ $c_2$ $:$ $d_M$ $c_M$

输出格式

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

题目大意

有 $N$ 名选手参加了 DDCC 20XX 初赛，但最多只能有 $9$ 名选手参加复赛。

初赛分许多轮，每一轮的规则是：

• 第一轮比赛所有 $N$ 名选手都要参加。
• 每一轮比赛剩余选手按以下规则制定：
  • 设剩余 $X$ 名选手，在 $X$ 的十进制形式中选择相邻两位，将它们删去，并在删去的位置上插入它们的和。比如，$2378$ 在选择百位和千位时会变为 $578$ ,选择十位和百位会变成 $2108$ ，选择个位和十位会变成 $2315$。$100$ 无论选择哪两位都会变成 $10$。
  • 当 $X\leq 9$ 时循环终止。

给定 $N$ ，求最多可以举行几轮比赛。

因为 $N$ 太大，所以给定两个序列 $d_1,d_2,...,d_M$ 和 $c_1,c_2,..,c_M$ , 意思是 $N$ 有 $c_1+c_2+...+c_M$ 为，它的前 $c_1$ 位都是 $d_1$，之后的 $c_2$ 位都是 $d_2$ ，以此类推。

2
2 2
9 1

3

3
1 1
0 8
7 1

9

提示

制約

• $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}$

Sample Explanation 1

この場合，予選の最初のラウンドには $N=229$ 人が参加します．大会の経過の一例として、次のパターンがありえます． - ラウンド $1$ に $229$ 人が参加し，ラウンド $2$ に $49$ 人が参加し，ラウンド $3$ に $13$ 人が参加し，本戦に $4$ 人が進出する． このとき，予選は $3$ ラウンド行われ、これが実は最適であることが分かります。

Sample Explanation 2

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