Problem Description

You are given a string $ S $ consisting only of digits from 1 to 9. You want to insert at most $ K $ commas (,) into this string to split it into multiple numbers.

Your goal is to minimize the maximum value of the numbers that appear after this operation, and then output that value.

Input Format

The input is provided from the standard input in the following format:

$ K $ $ S $

Output Format

Output the required integer in one line.

Sample Input and Output

Sample Input #1

2
15267315

Sample Output #1

315

Sample Input #2

0
12456174517653111

Sample Output #2

12456174517653111

Sample Input #3

8
127356176351764127645176543176531763517635176531278461856198765816581726586715987216581

Sample Output #3

5317635176

Notes/Hints

Constraints

• $ 0 ≦ K < |S| ≦ 100,000 $
• $ S $ consists only of digits from 1 to 9.

Partial Points

• For a dataset worth 100 points, $ |S| ≦ 2 $.
• For another dataset worth 100 points, $ |S| ≦ 16 $.
• For another dataset worth 200 points, $ |S| ≦ 100 $.
• For another dataset worth 200 points, $ |S| ≦ 2,000 $.

Sample Explanation 1

Splitting into $ 152 $, $ 67 $, $ 315 $ results in the maximum value being $ 315 $, which is the answer.

Sample Explanation 2

$ 12456174517653111 $ remains the answer as it cannot be split.

见题面 Input 部分

见题面 Output 部分