다리 건너기

깊은 협곡을 가로지르는 밧줄 다리가 있습니다. 사람들은 무리를 지어 다리를 건널 수 있지만, 한 무리의 인원은 최대 $M$명으로 제한됩니다. 한 무리가 다리를 건너는 데 걸리는 시간은 그 무리에서 가장 느린 사람의 시간으로 결정됩니다.

당신은 다리의 안전을 책임지며 무리를 편성하는 일을 맡고 있습니다. 사람들은 한 줄로 서서 대기하고 있고, 앞선 무리가 다리를 다 건너면 다음 몇 명에게 건너도 된다고 알립니다. 무리의 크기는 서로 달라도 되지만 어느 무리도 $M$명을 넘을 수 없으며, 대기 줄의 순서를 반드시 그대로 유지해야 합니다(각 무리는 줄의 맨 앞에서부터 연속된 사람들로 이루어집니다).

모든 사람을 건너게 하는 데 필요한 전체 시간, 즉 각 무리의 건너기 시간을 모두 합한 값을 최소로 만드세요.

첫째 줄에 정수 $M$ $(1 \le M \le 20)$이 주어집니다. 둘째 줄에는 대기 줄에 서 있는 사람 수 $Q$ $(1 \le Q \le 100)$가 주어집니다.

이어서 각 사람마다 두 줄이 주어집니다. 첫째 줄은 그 사람의 이름이고, 둘째 줄은 그 사람이 다리를 건너는 데 걸리는 개인 시간(음이 아닌 정수)입니다. 사람들은 주어진 순서대로 줄에 서 있습니다.

한 무리의 건너기 시간은 그 무리에 속한 사람들의 개인 시간 중 최댓값과 같음을 기억하세요.

대기 줄의 모든 사람을 건너게 하는 데 필요한 최소 전체 건너기 시간 $T$를 Total Time: T 형식으로 한 줄에 출력하세요.