题目描述

给定一个由 1 到 9 之间的数字组成的字符串 $S$。你可以在这个字符串中插入最多 $K$ 个逗号（,），将其分割成多个数字。

你的任务是使得插入逗号后产生的数字中的最大值最小。求出最小可能的最大值。

约束条件

• $0 ≤ K < |S| ≤ 100,000$
• $S$ 由 1 到 9 之间的数字组成。

部分得分

• 在价值为 $100$ 分的测试集中，$|S| ≤ 2$。
• 在价值为另外 $100$ 分的测试集中，$|S| ≤ 16$。
• 在价值为另外 $200$ 分的测试集中，$|S| ≤ 100$。
• 在价值为另外 $200$ 分的测试集中，$|S| ≤ 2,000$。

输入

输入以以下格式从标准输入给出：

$K$
$S$

输出

输出最小可能的最大值。

示例输入 1

2
15267315

示例输出 1

315

当字符串被分割成 $152$、$67$ 和 $315$ 时，这三个数字中的最大值是 $315$，也就是最小可能的最大值。

示例输入 2

0
12456174517653111

示例输出 2

12456174517653111

$12456174517653111$ 本身就是答案。

示例输入 3

8
127356176351764127645176543176531763517635176531278461856198765816581726586715987216581

示例输出 3

5317635176