008 - 宝くじ

問題

背景

働きたくない王国は働きたくない人間のための王国である。国民はいつも働かずに暮らす方法を考えている。そのため、宝くじはこの国で一番人気の高い娯楽となっている。

この国の宝くじは次のような仕組みになっている。 各くじにはくじ番号として 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 番目までの当選番号での賞金の合計額が最も多い宝くじの賞金の合計額を答えよ。

入力

n
a1 b1
:
an bn

制約

• 1 ≤ n ≤ 100,000
• 1 ≤ a_i ≤ 10⁹
• 1 ≤ b_i ≤ 10⁹
• a_i, b_i には leading zero が含まれないことに注意せよ。

出力

i 番目までの当選番号での賞金額の合計の最大値 c_i (1 ≤ i ≤ n) を i 行目に出力せよ。

入出力例

入力例1

4
11 100
1 10
10 150
21 200

出力例1

100
110
150
210