解题思路

本题要求从多个字符串中提取字符并构造一个长度为 K 的新字符串，且要使得构造出来的字符串字典序最小。具体的步骤可以分为以下几个阶段：

1. 问题分析

我们有 N 个字符串，每个字符串中有一个最大提取字符的限制 X_i。我们需要从每个字符串中提取字符并构成一个新字符串，使得新字符串的字典序最小，且总字符数为 K。

2. 核心思路

为了确保字典序最小，我们应该尽量优先选取字母较小的字符。因此，我们首先要从每个字符串中提取出字母并按字典序排列，然后在构建目标字符串时，每次都选取当前字母中最小的一个。

题目内容

多多在玩一个游戏，他想要从一堆字符串中构造出一个新的字符串，具体规则如下：

给定 $N$ 个字符串，多多可以从第 $i$ 字符串中提取出最多 $X_i$ 个字符，被取出字符可以按任意顺序拼接成一个长度为 $K$ 的新字符串 $T$，但多多希望这个字符串的字典序尽可能的小。

请问多多最终得到的新字符串是什么?

输入描述

第一行，两个整数 $N$ 和 $K$，表示有 $N$ 字符串以及目标串 $T$ 的长度。

接下来 $N$ 行，第 $i$ 行有一个字符串和一个整数：$S_i，X_i$。

$S_i$ 是第 $i$ 个字符串

$X_i$ 是要求第 $i$ 个字符串取出的字符个数

$1 <= N <= 1000$

$1 <= |S_i| <= 1000$

$0 <= X_i <= |S_i|$

$0 <= K <= \sum X_i<= 1000000$

输出描述

一个字符串 $T$

示例1

输入

2 3
abb 2
ccaa 1

输出

aab

说明

从第 $2$ 个字符串中取出 $a$，第 $1$ 个字符串中取出 $a$ 和 $b$，拼接成 $aab$ 的字典序最小。

示例2

输入

3 5
aaa 0
bab 2
aaa 3

输出

aaaab