시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB214736737.017%

문제

이 문제는 이기적인 목봉 체조 (Hard) 문제와 $N$ 제한 및 시간 제한을 제외하고 같은 문제이다.

대망의 유격 훈련 날, 조교는 훈련병들에게 목봉 체조 훈련을 시키려고 한다. 목봉 체조 훈련이란 여러 명이 동시에 하나의 목봉을 어깨높이로 들고, 반대편 어깨로 목봉을 옮기는 훈련이다.

조교들은 $N$명의 모든 훈련병들을 $M$개의 그룹으로 나눠서 목봉 체조를 실시하고자 한다. 이때, 훈련병들의 번호를 헷갈리지 않도록 서 있는 순서대로 연속된 훈련병들만 한 그룹으로 묶어야 하며, 각 그룹은 한 명 이상의 훈련병들로 구성되어야 한다.

하지만 이 훈련병들은 전부 다 너무 이기적이어서, 동일한 그룹에 본인보다 키가 조금이라도 큰 훈련병이 있다면 힘을 아예 쓰지 않고 드는 척만 한다. 즉, 그룹 안에서 키가 가장 큰 훈련병들만 목봉에 힘을 가한다.

$N$명의 훈련병을 적절히 $M$개의 그룹으로 나누었을 때 훈련병들이 들 수 있는 목봉 무게의 합의 최댓값을 구하여라.

입력

첫 번째 줄에 훈련병의 수 $N$과 그룹의 수 $M$이 공백으로 구분되어 주어진다. $(1\leq N\leq 1\,000;$ $1\leq M\leq 10;$ $M\leq N)$

두 번째 줄부터 $N+1$번째 줄까지, 훈련병의 키를 나타내는 정수 $h_i$와 힘을 나타내는 정수 $s_i$가 서 있는 순서대로 공백으로 구분되어 주어진다. $(1\leq h_i, s_i\leq 10^9)$

출력

$N$명의 훈련병을 적절히 $M$개의 그룹으로 나누었을 때 훈련병들이 들 수 있는 목봉 무게 합의 최댓값을 출력한다.

예제 입력 1

10 4
5 7
4 6
5 8
6 1
3 5
7 9
2 7
3 1
2 9
9 2

예제 출력 1

35

입력 순서대로 $1$번 훈련병부터 $N$번 훈련병이라고 하고, 하나의 그룹에 들어 있는 훈련병들을 중괄호 $\{\}$ 안에 넣어 표시하면, $\{1, 2, 3\}, \{4, 5, 6, 7, 8\}, \{9\}, \{10\}$ 으로 그룹을 묶으면 총 $35$의 무게를 들 수 있다.

출처

Contest > 보라매컵 > 제1회 보라매컵 본선 D번