34826번 - Yonsei TOTO 2 스페셜 저지

연세대학교는 다른 학교와 달리 수강신청을 할 때 마일리지 베팅 방식을 사용한다. 당신은 $N$개의 과목에 마일리지를 베팅해야 한다. 베팅 규칙은 다음과 같다.

1. 각 과목에는 $0$ 이상 $M$ 이하의 정수만큼 마일리지를 베팅해야 한다.
2. 모든 과목에 베팅한 마일리지의 총합은 $S$를 넘을 수 없다.

그러나 마일리지를 얼마나 베팅해야 수강신청에 성공할 수 있을지는 정확히 알 수 없다. 따라서 당신은 인기도라는 개념을 도입하여 어떤 과목에 마일리지를 베팅했을 때 수강신청에 성공할 확률을 다음과 같이 추측했다.

• $i$번째 과목에 $x$ 마일리지를 베팅했을 때, 수강신청에 성공할 확률은 $\min(\frac{x}{A_i} ,1)$이다.

이때 $A_i$는 $i$번째 과목의 인기도로, 그 과목을 $100\%$ 확률로 수강하기 위해 필요한 마일리지와 같다. 단, 인기가 매우 높아 $A_i\gt M$인 과목이 존재할 수 있음에 유의하라. 이 경우 최대치 $M$을 베팅해도 수강신청에 실패할 수 있다.

또한, 당신은 $i$번째 과목의 수강신청에 성공할 경우 $B_i$만큼, 실패할 경우 $0$만큼의 만족도를 얻는다. 이때, 만족도의 기댓값이 최대가 되는 마일리지 베팅 방법을 찾아보자.

첫째 줄에 과목의 수, 과목당 최대 마일리지, 총 마일리지를 나타내는 정수 $N$, $M$, $S$가 공백으로 구분되어 주어진다. ($1\leq N\leq 100\, 000$, $1\leq M\leq 1\, 000$, $M\leq S\leq N\times M$)

둘째 줄에 $i$번째 과목의 인기도를 나타내는 $N$개의 정수 $A_i$가 공백으로 구분되어 주어진다. ($1\leq A_i\leq 1\, 000$)

셋째 줄에 $i$번째 과목을 수강했을 때의 만족도를 나타내는 $N$개의 정수 $B_i$가 공백으로 구분되어 주어진다. ($1\leq B_i\leq 1\, 000$)

$N$개의 정수 $X_1,X_2,\cdots ,X_N$를 공백으로 구분하여 출력한다. 이는 $i$번째 과목에 $X_i$ 마일리지를 베팅하는 것을 의미하며, 모든 $i$에 대해 $0\leq X_i\leq M$이고, $\sum_{i=1}^{N}{X_i}\leq S$를 만족한다.

기댓값이 최대가 되는 베팅 방법이 여러 가지일 경우, 그중 아무것이나 출력한다.