To escape the loneliness of working remotely everyday, Erika decided to try on 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 well visible and thus each statue needs to be placed under a distinct

street light. Further, the arrangement should be aesthetic which means that the statues should be

placed by increasing size with the smallest statues near the beginning of the street and the biggest ones

near the end.

Erika placed her statues but she forgot to place them in increasing size and now she has to reposition

them in accordance to both of her desires.

The street has N evenly spaced street lights numbered from 1 at the beginning of the street to N at

the end of the street. You estimate the time required to move a statue of size s from the street light i

to the light j as taking Erika s × |i − j| units of time. You ask yourself, how much time does it take

to reposition all statues knowing that she will use the fastest way possible? Note that she may put

statues under street lights that do not have statues at the moment.

输入描述:

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

输出描述:

The output should contain a single line containing a single integer: the minimum amount of time
needed to move statues such that each statue is under a different street light and such that the size of
statues grows with the street light numbers under which they are.

3 3
1 3
2 2
3 1

8

Because there are as many street lights as there are statues we needto position the statue of size 1 at street light 1 (which takes units of times), leave the statue of size 2 atstreet light 2, and move the statue of size 3 to the street light 3(which takes units of times). In total this takes units of time.

4 3
2 2
3 2
4 1

3

The fastest way of fixing the ordering of statues is to move 
the statue of size 1 to the street light 1 for a total time of .

备注:

for all ,,