ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#6242

케이크 만들기 4s 256MB

問題

총 N개의 케이크 조각들이 있고, 각 조각은 맛 V_i과 색 C_i를 가지고 있다. 이제 이 중 M개를 뽑아 원형으로 이어 케이크를 만들 것이다.

순서대로 k_1, ..., k_M번 조각을 뽑았을 때 만든 케이크의 가치는 다음과 같이 표현할 수 있다. 만들 수 있는 케이크의 가치의 최대값을 구해보자.

\sum_{j=1}^{M} V_{k_j}+\sum_{j=1}^{M} |C_{k_j}-C_{k_{j+1}}| (단, k_{M+1}=k_1)


入力

첫 줄에 케이크 조각의 수 N과 선택할 조각의 수 M이 공백으로 구분되어 주어진다. (3\leq M\leq N\leq 200000)

그 다음 N개의 줄에 걸쳐 각 조각의 정보 V_i와 C_i가 공백으로 구분되어 주어진다. (1\leq V_i, C_i\leq 10^9)


出力

만들 수 있는 케이크의 가치의 최대값을 한 줄에 출력하여라.


部分問題

番号 点数 条件
#110点

N\leq 100

#220点

N\leq 2000

#370点

제한 없음


例題 #1

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

例題 #2

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

出典

JOISC 2019 Day 4
ログインしないとコードを書けません。