Bridge Crossing

Interview

Time limit1sMemory limit128 MB

Summary

Split a line of people into consecutive groups of at most M, where each group costs its slowest member's time, and minimize the total cost.

Level: Medium4 of 10
Topics: Dynamic programming, Array, Sliding window, Queue
Solved: No attempts yet

Problem

A rope bridge spans a deep gorge. People may cross the bridge in groups, but a group may contain at most $M$ people. The time taken for a group to cross is determined by its slowest member.

You are responsible for safety on the bridge and control how the groups are formed. People wait in a single line; once the previous group has finished crossing, you tell the next few people that they may cross. Groups may have different sizes, but no group may contain more than $M$ people, and the order of the people in the line must be preserved (each group consists of consecutive people taken from the front of the line).

Determine the minimum total crossing time needed to get everyone across, where the total time is the sum of the crossing times of all the groups.

Input

The first line contains an integer $M$ $(1 \le M \le 20)$ . The second line contains $Q$ $(1 \le Q \le 100)$ , the number of people waiting in the line.

For each person, two lines follow: the first is the person's name, and the second is that person's individual crossing time (a non-negative integer). The people stand in the line in the given order.

Recall that a group's crossing time equals the maximum individual crossing time among the people in that group.

Output

Output the minimum total crossing time $T$ needed for the entire line to cross, on a single line in the form Total Time: T.

Examples2

Example 1

Input

2
5
alice
1
bob
5
charlie
5
dobson
3
eric
3

Expected output

Total Time: 9

Example 2
Input
```
1
4
a
3
b
7
c
2
d
5
```
Expected output
```
Total Time: 17
```