좌석

시간 제한2초메모리 제한512 MB

요약

N명의 승객 중 K명을 L석 좌석에 앉혀, 각 승객의 A_i와 인접한 빈자리당 B_i의 합을 최대화하는 값을 K마다 구합니다.

문제

X 도시의 지하철은 조금 특이하다. 열차는 객차 한 칸으로 이루어져 있고, 객차에는 한 줄로 늘어선 좌석이 $L$ 개 있다. 객차에는 $0$ 번부터 $N-1$ 번까지 번호가 붙은 승객이 $N$ 명 타고 있다. 각 승객의 쾌적함은 다음과 같이 정해진다.

승객이 서 있으면 쾌적함은 $0$ 이다.
승객이 앉으면 앉는 것만으로 $A_i$ 의 쾌적함을 얻고, 그 승객과 이웃한 승객 또는 좌석 끝 사이에 있는 빈 좌석마다 $B_i$ 의 쾌적함을 추가로 얻는다.

예를 들어 승객이 3명이고 $A_0=5$ , $B_0=2$ , $A_1=10$ , $B_1=1$ , $A_2=1$ , $B_2=1$ 이며 좌석이 $L=6$ 개라고 하자. 빈 좌석을 _로 나타내면 다음과 같이 앉아 있는 경우를 생각할 수 있다.

_ 0 _ _ 1 _

승객 2는 서 있다.

모든 승객의 쾌적함 합계는 $24$ 이다.

$N$ , $L$ 과 각 승객의 특성이 주어졌을 때, 앉은 승객 수가 $1$ 명부터 $N$ 명까지인 각 경우에 대해 쾌적함 합계의 최댓값을 구하는 프로그램을 작성하라.

첫 번째 줄에 승객 수 $N$ 과 좌석 수 $L$ 이 두 정수로 주어진다. 이어지는 $N$ 개의 줄에는 승객 $i$ 의 특성인 음이 아닌 정수 $A_i$ 와 $B_i$ 가 주어진다.

$N$ 개의 줄을 출력한다. $K$ 번째 줄에는 정확히 $K$ 명이 앉아 있을 때 승객들이 얻을 수 있는 쾌적함 합계의 최댓값을 출력한다. $K > L$ 이면 $K$ 명을 $L$ 개의 좌석에 앉히는 유효한 배치가 없으므로 $0$ 을 출력한다.