Statues

Interview

Time limit1sMemory limit512 MB

Summary

Given K statues at distinct street lights with sizes, assign them to distinct lights so sizes increase with position, minimizing total movement cost size times distance.

Level: Medium7 of 10
Topics: Dynamic programming, Sorting, Greedy, Divide and conquer
Solved: No attempts yet

Problem

To escape the loneliness of working remotely every day, Erika decided to try a new hobby: sculpture. She already has a large collection of statues, and the municipality has allowed her to show her art outside.

Erika wants her statues to be clearly visible, so each statue needs to be placed under a distinct street light. The arrangement should also be aesthetic: the statues should be placed in increasing order of size, with the smallest statues near the beginning of the street and the largest near the end.

Erika placed her statues but forgot to put them in increasing order of size, and now she has to reposition them to satisfy both of her wishes.

The street has N evenly spaced street lights, numbered from 1 at the beginning of the street to N at the end. You estimate the time needed to move a statue of size s from street light i to street light j as s × |i − j| units of time. Erika will use the fastest way possible. How much time does it take to reposition all the statues? She may place statues under street lights that have no statue at the moment.

Input

The first line contains two space-separated integers: N, the number of street lights, and K, the number of statues. Each of the following K lines contains two space-separated integers, the i + 1-th line containing Pi and Si, which describe the i-th statue. Pi is the number of the street light under which the statue is, and Si is its size.

Output

Print a single integer on one line: the minimum time needed to move the statues so that each statue is under a different street light and the sizes of the statues grow with the street light numbers under which they stand.

Constraints

1 ≤ K ≤ N ≤ 5 000
for all 1 ≤ i ≤ K, 1 ≤ Si ≤ 1 000 000, 1 ≤ Pi ≤ N

Examples2

Example 1
Input
```
3 3
1 3
2 2
3 1
```
Expected output
```
8
```
Example 2
Input
```
4 3
2 2
3 2
4 1
```
Expected output
```
3
```