시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 256 MB 9 5 5 55.556%

문제

Today is IOI-chan’s birthday, so her brother JOI-kun pre-ordered her birthday cake. Though he planned to buy a whole cake, he mistakenly ordered N pieces of cake. They are numbered from 1 to N and each piece of cake has value and color. The value of the piece i (1 ≤ i ≤ N) is Vi and the depth of its color is Ci.

In order to make a whole cake, he decided to choose M distinct pieces and to arrange them in a circular form in an arbitrary order. The beauty of the whole cake he makes is defined as

\[\sum_{j=1}^{M}{V_{k_j}} - \sum_{j=1}^{M}{\left|C_{k_j} - C_{k_{j+1}}\right|}\]

if he chooses the pieces k1, . . . , kM and arranges them in this order (here we set kM+1 = k1). In other words, the beauty of the whole cake is the sum of the values of its pieces minus the sum of the differences in the depth of the color between every two adjacent pieces. JOI-kun wants to make the whole cake as beautiful as possible.

Write a program which, given the number of pieces, the number of pieces needed to make a whole cake, the value and the depth of color for each piece, calculates the maximum beauty of a whole cake JOI-kun can make.

입력

Read the following data from the standard input. All the values in the input are integers.

N M
V1 C1
:
VN CN

출력

Write one line to the standard output. The output should contain the maximum beauty of the whole cake JOI-kun can make.

제한

  • 3 ≤ N ≤ 200 000.
  • 3 ≤ M ≤ N.
  • 1 ≤ Vi ≤ 1000 000 000 (1 ≤ i ≤ N).
  • 1 ≤ Ci ≤ 1000 000 000 (1 ≤ i ≤ N).

예제 입력 1

5 3
2 1
4 2
6 4
8 8
10 16

예제 출력 1

6

If JOI-kun chooses the pieces 1, 3 and 2 and arranges them in this order, the sum of the values of its pieces is 2 + 6 + 4 = 12 and the sum of the differences in the depth of the color is |1 − 4| + |4 − 2| + |2 − 1| = 6. Thus, the beauty of the whole cake is 12 − 6 = 6.

He can also make a whole cake with beauty 6 if he chooses the pieces 2, 3 and 4 and arrange them in this order.

Since he cannot make a more beautiful whole cake, you should output 6.

예제 입력 2

8 4
112103441 501365808
659752417 137957977
86280801 257419447
902409188 565237611
965602301 689654312
104535476 646977261
945132881 114821749
198700181 915994879

예제 출력 2

2323231661