分数: 600 点
问题陈述
在字符串公平中,他们确定 非空字符串的 美女 非空字符串的 S 由小写英文字母组成。
弦之美 S 等于 N 分数由 N 标准。 对于 i = 1, 2, \ldots, N,分数由 i- 第一个标准是 “字符串出现的次数 T_i (长度 最多 3 在输入中给出) S 作为连续子序列”乘以 P_i.
打印最大可能的美丽 非空 字符串 S 由小写英文字母组成。
如果可以获得无限大的美,打印 Infinity 。
这里,字符串出现的次数 字符串中的 V 在一个字符串中 U = U_1U_2\ldots U_{|U|} 作为连续子序列被定义为 整数的个数 i 这样 1 \leq i \leq |U|-|V|+1 和 U_iU_{i+1}\ldots U_{i+|V|-1} = V.
约束
- 1 \leq N \leq 18278
- N 是一个整数。
- T_i 是长度介于 1 和 3 由小写英文字母组成。
- i \neq j \Rightarrow T_i \neq T_j
- -10^9 \leq P_i \leq 10^9
- P_i 是一个整数。
输入
输入由标准输入按以下格式给出:
N T_1 P_1 T_2 P_2 \vdots T_N P_N
输出
打印最大可能的美丽 非空 字符串 S 由小写英文字母组成。
如果可以获得无限大的美,打印 Infinity 。
示例输入 1
3 a -5 ab 10 ba -20
示例输出 1
Infinity
例如,如果 S = abzabz:
- 分数由 1-st 标准是 2 \times (-5) = -10 点,因为
a出现两次 S 作为连续的子序列。 - 分数由 2-nd 标准是 2 \times 10 = 20 点,因为
ab出现两次 S 作为连续的子序列。 - 分数由 3-rd 标准是 0 \times (-20) = 0 点,因为
ba发生 0 次 S 作为连续的子序列。
因此,美丽 S is (-10) + 20 + 0 = 10.
作为另一个例子,如果 S = abzabzabz:
- 分数由 1-st 标准是 3 \times (-5) = -15 点,因为
a发生 3 次 S 作为连续的子序列。 - 分数由 2-nd 标准是 3 \times 10 = 30 点,因为
ab发生 3 次 S 作为连续的子序列。 - 分数由 3-rd 标准是 0 \times (-20) = 0 点,因为
ba发生 0 次 S 作为连续的子序列。
因此,美丽 S is (-15) + 30 + 0 = 15.
一般来说,对于正整数 X,如果 S 是一个串联 X 副本 abz,那么美丽 S is 5X。
既然你想要多大的美就可以得到多大的,
应打印 Infinity 。
示例输入 2
28 a -5 ab 10 ba -20 bb -20 bc -20 bd -20 be -20 bf -20 bg -20 bh -20 bi -20 bj -20 bk -20 bl -20 bm -20 bn -20 bo -20 bp -20 bq -20 br -20 bs -20 bt -20 bu -20 bv -20 bw -20 bx -20 by -20 bz -20
示例输出 2
5
S = ab 实现最大程度的美观。
示例输入 3
26 a -1 b -1 c -1 d -1 e -1 f -1 g -1 h -1 i -1 j -1 k -1 l -1 m -1 n -1 o -1 p -1 q -1 r -1 s -1 t -1 u -1 v -1 w -1 x -1 y -1 z -1
示例输出 3
-1
请注意 S 应该是一个非空字符串。