反子序列

题目描述

33DAI 有一袋字符。他给了 Tom 三个东西：

• 一个整数 $n$，表示他要拼出的字符串长度；
• 一袋字符，也就是 $k$ 种字符各自有多少个；
• 一个字符串 $t$。

33DAI 要用袋子里的字符（每个字符最多用一次，可以不全部用完）拼出一个长度恰好为 $n$ 的字符串 $s$，使得 $t$ 是 $s$ 的子序列。

Tom 想让 33DAI 拼出的字符串字典序最小。请你帮他求出这个字符串；如果拼不出来，输出 $-1$。

• 子序列：从 $s$ 中删掉若干个字符（可以删 $0$ 个），剩下的字符按原顺序拼成的字符串。
  • 例如 abc 的子序列有 a、c、ac、abc、bc 等，但 ca 不是。
• 字典序：从第一个字符开始逐个比较，第一个不同的字符较小的那个字符串更小；如果一个是另一个的前缀，则短的更小。

输入格式

第一行三个整数 $n,k,m$，分别表示要拼的长度、有几种字符、$t$ 的长度。

接下来 $k$ 行，每行一个字符 $c_i$ 和一个整数 $cnt_i$，表示袋子里有 $cnt_i$ 个字符 $c_i$。

最后一行一个长度为 $m$ 的字符串 $t$（$m=0$ 时这一行是空行）。

输出格式

一行：字典序最小的满足条件的字符串；若无解，输出 $-1$。

样例

4 1 0
a 4

aaaa

4 3 2
a 1
b 1
c 2
ab

abcc

样例说明

样例 1： 只有字符 a，有 $4$ 个，要拼长度 $4$，目标串是空串（空串是任何字符串的子序列）。唯一的拼法是 aaaa。

样例 2： abcc

数据范围

对于全部数据，$0\le n\le 10^{5}$，$0\le k\le 26$，$0\le m\le 10^{5}$，$c_i$ 均为小写英文字母且互不相同，$cnt_i\ge 0$，所有 $cnt_i$ 之和不超过 $10^{5}$。

每个子任务的计分方式为 min（取该子任务中所有测试点的最低分）。

子任务之间存在依赖：子任务 2 依赖子任务 1，子任务 3 依赖子任务 2。即只有通过了所依赖的子任务，该子任务才能得分。