分数: 500 点
问题陈述
N 程序员将参加DDCC 20XX的预赛阶段。不过由于场地的大小,最多 9 参赛者可参加决赛。
预赛由几轮组成,具体如下:
- 所有 N 参赛者将参加第一轮。
- 当 X 选手参加某轮比赛,晋级下一轮的选手人数将按如下方式决定:
- 主办方将选择十进制中连续两位数字 X,并将它们替换为这些数字的总和。得出的数字将是晋级下一轮的参赛者人数。
例如,当 X = 2378,晋级下一轮的参赛者人数为 578 (如果 选择 2 和 3 ), 选择 2108 (如果 选择 3 和 7 ),或 选择 2315 (如果 选择 7 和 8 )。
当 X = 100,晋级下一轮的参赛者人数为 10,无论选择哪两位数字。
- 主办方将选择十进制中连续两位数字 X,并将它们替换为这些数字的总和。得出的数字将是晋级下一轮的参赛者人数。
- 预赛阶段结束时 9 或更少的参赛者剩余。
首席组织者林戈希望举办尽可能多的比赛。 求出预赛阶段的最大可能回合数。
由于参赛人数较多, N,可以是巨大的,它以两个整数序列的形式提供给您 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 参赛者将参加第一轮。初步阶段的一种可能的进展如下:
- 229 参赛者参加回合 1, 49 参赛者参加回合 2, 13 参赛者参加回合 3,和 4 选手晋级决赛。
这里,预赛阶段进行三轮,这是可能的最大数量。
示例输入 2
3 1 1 0 8 7 1
示例输出 2
9
在这种情况下, 1000000007 将参加第一轮。