Yonsei TOTO 2

시간 제한1초메모리 제한1024 MB

요약

각 과목에 최대 M, 총합 S 이하로 마일리지를 배분해 성공 확률 min(x/A_i, 1)일 때 기대 만족도의 합을 최대로 만드는 베팅을 구한다.

난이도: 보통10점 중 7점
유형: 그리디, 수학, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

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

각 과목에는 $0$ 이상 $M$ 이하의 정수만큼 마일리지를 베팅해야 한다.
모든 과목에 베팅한 마일리지의 총합은 $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$ 를 만족한다.

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

예제2

예제 1

입력

6 36 72
1 10 20 34 50 72
1 10 20 100 10 200

예상 출력

1 1 0 34 0 36

예제 2
입력
```
2 36 72
1 1
1000 1000
```
예상 출력
```
36 36
```