페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
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
로그인해야 코드를 작성할 수 있어요.