케이크 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$).