보석 도둑

큰 박물관이 세계 각지의 보석을 모은 특별전을 열었다. 도둑 에드워드 테레난도는 이 전시장에서 자기 인생 최대의 도둑질을 계획하고 있다.

에드워드는 훔친 보석의 가치 합을 최대로 만들고 싶으므로 어떤 보석을 집을지 신중하게 골라야 한다.

에드워드에게는 크기가 $1, 2, 3, \dots, k$인 배낭이 하나씩 있다. 크기가 $s$인 배낭에는 크기의 합이 $s$ 이하인 보석을 담을 수 있다. 배낭 크기마다 담을 수 있는 보석 가치 합의 최댓값을 구하라.

한 배낭에 같은 보석을 두 번 담을 수는 없고, 배낭마다 서로 독립인 문제로 푼다.

첫째 줄에 보석의 개수 $n$과 배낭의 최대 크기 $k$가 공백을 사이에 두고 주어진다 ($1 \le n \le 1{,}000{,}000$, $1 \le k \le 100{,}000$).

다음 $n$개의 줄에는 보석 하나의 정보가 한 줄씩 주어진다. 각 줄에는 보석의 크기 $s$와 가치 $v$가 공백을 사이에 두고 주어진다 ($1 \le s \le 300$, $1 \le v \le 10^9$).

한 줄에 정수 $k$개를 공백 하나로 구분해 출력한다. $i$번째 정수는 크기가 $i$인 배낭에 담을 수 있는 보석 가치 합의 최댓값이다.