Во предградијата на еден голем град има долги улици покрај кои има големи згради со многу жители. Во една таква улица има N згради, а во секоја зграда има одреден број на ученици кои наутро треба да бидат однесени во локалното училиште. Школскиот автобус кој ги собира, за да е брз, смее да застане само пред K од овие згради. Така, дел од учениците ќе мора да пешачат од нивната зграда до некоја зграда пред која застанува автобусот.

Целта ни е да ги избереме К-те локации на кои ќе застанува автобусот на тој начин што ќе имаме минимално пешачење. Пешачењето е збир од пешачењата на сите ученици кои пешачат, а пешачењето на секој ученик е |x_i - x_j|, т.е. растојанието меѓу зградата на локација x_i во која живее и зградата на локација x_j, до која пешачи.

За дадени N згради со нивните локации, бројот на ученици во секоја од нив, и даден број K - број на места на застанување на автобусот, пресметајте го минималното вкупно пешачење, при најоптимален распоред на местата за застанување.

Влез

Првиот ред содржи два цели броја: N (бројот на згради) и K (бројот на места за застанување на автобусот), (1 ≤ K < N ≤ 5000).

Секој од следните N редови содржи по два цели броја кои ги претставуваат:
x_i (локацијата на зградата долж патот).
s_i (бројот на ученици во таа зграда).
1 ≤ x_i, s_i ≤ 1 000 000.

Напомена: Зградите се дадени по ред според нивната локација x_i, од најпрва до најпоследна локација.

Забелешка.
За 40% од поените ќе важи: 1 ≤ K < N ≤ 500
За дополнителни 20% од поените ќе важи: 1 ≤ K < N ≤ 1000

Излез

Отпечатете еден цел број - бараниот одговор.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 128 megabytes

Примери

влез
3 1
20 1
30 1
40 1

излез
20

влез
3 1
11 3
12 2
13 1

излез
4

влез
6 2
10 15
12 17
16 18
18 13
30 10
32 1

излез
182

Објаснување за првиот пример:
Треба да ги собереме учениците од сите N = 3 згради на едно место (бидејќи K = 1). Зградите се на еднакво растојание и секоја има по еден ученик. Најисплатливо е автобусот да застане кај зградата на x = 30, а да пешачат учениците од зградите на x = 20 и x = 40. На тој начин, минималното вкупно пешачење изнесува 20.

Објаснување за третиот пример:
Треба да ги собереме учениците од N = 6 згради на K = 2 локации за застанување на автобусот. Можеме да го минимизираме пешачењето на следниов начин:
- Учениците од зградите на x = 10, x = 16, и x = 18 ќе пешачат до зградата на x = 12.
- Ученикот од училиштето на x = 32 ќе пешачи до зградата на x = 30.