The annual Hong Kong Olympiad In Dancing Industry (HKOI) has begun. The contest format requires a team of $N$ dancers to perform a relay routine on a long straight runway.

Alice’s team has prepared for a long time, and now it's their turn. However, a sudden storm has caused $M$ water puddles to form along the runway in a fixed sequence. The $i$ th puddle has a length of $L_i$.

However, the show must go on. Alice's Team decided not to give up due to the rain. They decided to embrace the rain and continue to complete their routine.

To complete the routine, the $M$ puddles must be divided among the $N$ dancers according to the following rules:

1. Contiguous Segment: The puddles are arranged in a specific order and cannot be rearranged. Each dancer must handle a contiguous segment of puddles. (e.g., Dancer 1 takes puddles 1 to 3, Dancer 2 takes puddles 4 to 6, etc.).

2. No Division: Every puddle must be assigned to exactly one dancer. Dancers cannot split the puddle into smaller puddles and share it.

As the captain, Alice wants to distribute the work such that the team is as safe as possible. Specifically, she wants to minimize the maximum length of water puddle experienced by any single dancer.

Help Alice figure out: What is the lowest possible value for the maximum total puddle length assigned to a single dancer?

Input

The first line consists of 2 integers, $N$, $M$.($1\le N, M \le 10^5$)
The following line consists of $M$ integers $L_1,L_2,...,L_M$, where $L_i$ represents the length of the $i$ th water puddle. ($1\le L_i \le 10^9$ for all $1 \le i \le M$)

Output

The output consists of a single integer, the lowest possible value for the maximum total puddle length assigned to a single dancer.

Subtasks

Subtask 1: $N$ = 1 (5 pts)
Subtask 2: $M$ = 1 (5 pts)
Subtask 3: $1 \le N, M, L_i \le 100$ (60 pts)
Subtask 4: No additional constraints (30 pts)

Hint

Remember to use long long int instead of int, as the answer may exceed $2^{31}-1$