모듈러 배낭 문제

시간 제한1.5초메모리 제한256 MB

요약

가중치와 비용이 있는 n개의 물건과 소수 p가 주어질 때, 각 나머지 r마다 무게 합을 p로 나눈 나머지가 r인 부분집합의 비용 최댓값을 구합니다.

난이도: 어려움10점 중 9점
유형: 동적 계획법, 정수론, 그리디
정답자: 아직 제출이 없습니다

문제

오늘은 특이한 배낭 문제를 풀어 보자. 물건이 $n$ 개 있고, $i$ 번째 물건의 무게는 $w_i$ , 비용은 $c_i$ 이다. 또 소수 $p$ 가 주어진다. $p$ 로 나눈 나머지가 $r$ 인 각 값에 대해, 총 무게를 $p$ 로 나눈 나머지가 $r$ 인 물건 집합의 비용 합의 최댓값을 구하라. 샘플을 제외한 각 테스트의 무게와 비용은 $[0 \dots 10^9]$ 범위에서 무작위로 서로 독립적으로 뽑힌다. $n$ 과 $p$ 는 직접 정한 값이다.

입력

첫 줄에 두 정수 $n$ , $p$ ( $1 \leq n \leq 10^6$ , $2 \leq p \leq 3000$ )가 주어진다. 각각 물건의 개수와 나머지를 구할 소수이다.

다음 줄에는 $n$ 개의 정수 $w_i$ ( $0 \leq w_i \leq 10^9$ )가 주어진다. 물건의 무게이다.

그다음 줄에는 $n$ 개의 정수 $c_i$ ( $0 \leq c_i \leq 10^9$ )가 주어진다. 물건의 비용이다.

출력

한 줄에 정수 $p$ 개를 출력한다. $i$ 번째 정수(0부터 시작)는 총 무게를 $p$ 로 나눈 나머지가 $i$ 인 물건 집합의 비용 합의 최댓값이다. 그런 집합이 없으면 -1을 출력한다.

예제2

예제 1
입력
```
2 2
1 2
1 1
```
예상 출력
```
1 2
```
예제 2
입력
```
2 2
2 2
1 1
```
예상 출력
```
2 -1
```