케이크 3

오늘은 IOI양의 생일이다. 이 날을 위해 JOI군은 생일 케이크를 예약했다. 원형 케이크 하나를 통채로 예약할 생각이었지만 착오가 있어서 $N$조각의 케이크를 예약해 버렸다. 각 조각에는 1번 부터 $N$번까지 번호가 붙어 있고, $i$ 번째 ($1 \le i \le N$) 조각의 가치는 $V\_i$이고, 색의 짙음은 $C\_i$이다.

JOI군은 서로 다른 $M$개의 케이크를 골라, 원하는 순서대로 배열해 합쳐서 원형 케이크를 만들기로 결심했다. 케이크 조각들이 $k\_1$번, $\cdots$, $k\_M$번 조각의 순서로 나열되어 있을 때, 이 케이크의 아름다움은

$\sum\_{j=1}^{M} {V\_{k\_j}} - \sum\_{j=1}^{M} {\left| C\_{k\_j} - C\_{k\_{j+1}}\right|}$

으로 정의된다. (단, $k\_{M+1} = k\_1$ 이다.) 즉, 아름다움은 사용된 케이크 조각의 가치의 합으로 부터 인접한 두 케이크의 색의 짙음에 차의 절댓값의 합계로 정의된다. JOI군은 되도록이면 원형 케이크의 가치의 합을 최대로 하고싶다.

케이크 조각의 갯수, 각 케이크 조각의 가치와 색의 짙음, 원형 케이크를 만들기 위해 필요한 조각의 갯수가 주어졌을 때, JOI군이 만들 수 있는 원형 케이크의 아름다움의 최댓값을 구하는 프로그램을 작성하여라.

표준 입력에서 다음과 같은 형식으로 주어진다. 모든 값은 정수이다.

$N$ $M$

$V\_1$ $C\_1$

$\vdots$

$V\_N$ $C\_N$

표준 출력으로 한 개의 줄에 하나의 수를 출력하여라. 이는 JOI군이 만들 수 있는 원형 케이크의 아름다움의 최댓값이다.

• $3 \le N \le 200\ 000$.
• $3 \le M \le N$.
• $1 \le V\_i \le 1\ 000\ 000\ 000$ ($1 \le i \le N$).
• $1 \le C\_i \le 1\ 000\ 000\ 000$ ($1 \le i \le N$).