← 返回题目列表

AtCoder · utpc2014_e

E. 彩票

中文机器翻译题面 查看原题

問題

背景

不想工作的王国是为不想工作的人准备的王国。国民总是在考虑如何不用工作就能生活。因此,彩票成为这个国家最受欢迎的娱乐活动。

这个国家的彩票机制如下。每张彩票上都有 1 个正整数作为彩票号码。存在一些中奖号码和奖金,对于每个中奖号码,持有以其结尾的号码的彩票,将获得相应的奖金。例如,如果中奖号码是 100 ,相应的奖金是 200 ,那么彩票号码为 100 呀 请注意,它可能是 2100 的彩票将获得 200 的奖金。

幸或不幸,你作为这个国家最勤劳的人,被指派负责彩票开奖的现场直播。在现场直播中,每次会公布 1 个中奖号码及对应奖金,每次都需要公布 1 张彩票中理论上能获得的最高奖金。

国民对彩票的热情非常高涨,现场直播的失误是绝对不允许的。因此,为了准确完成这项大任务,并且在直播期间能在家休息,你决定编写程序来求出所需的数值。

課題

彩票的中奖号码及其奖金由 n 。 i (1 ≤ i ≤ n) 个中奖号码和 a_i 奖金构成,均以整数形式给出,当 b_i 的位数为a_i 时,与 m 一致的彩票将获得对应奖金 m 数字是 满足 a_i 。 b_i 被给予。例如,当中奖号码为 100 时,下3数字是 满足 100 的那种彩票,即号码为 100 的彩票或 2100 的彩票将获得奖金。请回答在各 i (1 ≤ i ≤ n) , 当我输入i 个中奖号码中的奖金总额最多的彩票的奖金总额。

配点

200

入力

n
a_1 b_1
:
a_n b_n

制約

  • 1 ≤ n ≤ 100,000
  • 1 ≤ a_i ≤ 10^9
  • 1 ≤ b_i ≤ 10^9
  • a_i, b_i 不包含前导零。

出力

i 到第几名的中奖号码奖金总额的最大值 c_i (1 ≤ i ≤ n) 该值应乘以 i 上输出。

入出力例

入力例1

4
11 100
1 10
10 150
21 200

出力例1

100
110
150
210