Tiampist

This problem is adapted from CCO 2015 Day2 T2 "Tiampist".

A timpanist (a drum player) is about to perform a measure consisting of N notes. There are D timpani (drums) available, numbered from 1 to D. Each note i is played for T_i seconds and must be played at pitch P_i. In this problem the 12 possible pitches in one octave are represented by the integers 1 through 12 corresponding to the notes

[ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \ \hline \text{F} & \text{F}^{\sharp} & \text{G} & \text{G}^{\sharp} & \text{A} & \text{A}^{\sharp} & \text{B} & \text{C} & \text{C}^{\sharp} & \text{D} & \text{D}^{\sharp} & \text{E} \ \hline \end{array} ]

Before the performance the drums can be arbitrarily tuned; however, during the performance a drum can play a note only if at that very moment its tuning exactly equals the required pitch. Moreover, a drum cannot be adjusted at the same time it is playing its note, and the drummer is only able to adjust one drum at a time. There is one more twist: at every moment the drum tunings must satisfy an ordering constraint, namely if the drums are numbered 1 through D, then drum i+1 must always be tuned to a pitch strictly higher than drum i (this applies only to drums that have been used – unused drums may be set arbitrarily at the start of any gap).

The performance goes through the N notes in order. For each drum, whenever it is used for a note after its previous use, if its current tuning does not match the new note’s pitch then it must be adjusted during a gap between notes. The time required to adjust a drum from pitch \(a\) to \(b\) is \(|a-b|\) seconds. (Note that if a drum is used for its first note, no adjustment cost is incurred.)

The drummer wishes to maximize his overall free time during the performance to perform fine adjustments – that is, he wants to maximize the total time in which he is not forced to make rapid adjustments. Since the overall performance duration is \(\sum_{i=1}^{N}T_i\) and the only time lost is the cumulative adjustment time, your task is to assign each note to a drum (each drum may play several notes, in the order they occur) and decide when to adjust each drum so that the total adjustment time (i.e. the sum of all required tuning changes) is minimized. Then, the answer is computed as

[ \text{Answer} = \sum_{i=1}^{N}T_i - \text{(minimum total adjustment cost)}. ]

Note: When a drum is chosen to play a note at time i, its tuning instantly becomes \(P_i\). However, the ordering condition must be maintained at every note: if drum d plays the current note, then for every drum r that has been used before, the following must hold:

• For every drum r with r < d, if it has been used (its last tuning is P), then \(P_{r} < P_i\).
• For every drum r with r > d that has been used, \(P_i < P_{r}\).

Your goal is to plan the assignment so that the cumulative required adjustment cost is as low as possible.

inputFormat

The input begins with a line containing two integers D and N (1 ≤ D ≤ N, N is small).

Then follow N lines. The i-th line contains two integers: T_i (the time in seconds allocated to note i) and P_i (an integer between 1 and 12 representing the pitch of note i).

outputFormat

Output a single integer – the maximum total adjustment time available, computed as

[ \sum_{i=1}^{N}T_i - \text{(minimum total tuning adjustment cost)}. ]

You may assume that an assignment satisfying the ordering constraints exists.

sample

2 5
5 3
3 1
4 3
2 5
6 3

16