32758번 - N+1 행사

문제

어느 편의점에는 1ドル+1$ 행사, 2ドル+1$ 행사가 있다. 당신이 방문한 편의점은 이를 확장하여 각 상품에 대해 다양한 $N+1$ 행사를 진행하고 있었다. 편의점 상품의 종류는 1ドル$번부터 $M$번까지 번호가 매겨져 있고, 각 $i$번 상품에 대한 행사값 $n_i$가 있다. 이는 $i$번 상품을 $n_i$개 구매할 경우, $i$번 상품을 1ドル$개 더 준다는 뜻이다.

해당 편의점은 소비자가 극한의 이득을 취할 수 있도록, 특별히 $N+1$ 행사로 받은 상품 또한 $N+1$ 행사에 사용할 수 있는 상품으로 쳐 주었다. 즉, 만약 2ドル+1$ 행사 상품이 있고 해당 상품을 3ドル$개 구매한다면, 해당 상품을 총 5ドル$개 받을 수 있다. 단, 이미 $N+1$ 행사에 사용한 상품을 $N+1$ 행사에 다시 사용할 수는 없다.

당신은 $i$번 상품에 대해 가져가고 싶은 상품의 목표 개수 $a_1, a_2, a_3, \cdots, a_M$를 설정했다. $N+1$ 행사를 이용하여 가져가고 싶은 각 상품 목표 개수를 모두 만족시키려면, 각 상품을 최소 몇 개 구매해야 하는지 모두 출력해 보자.

입력

첫 번째 줄에 편의점 상품 종류의 개수 $M$이 주어진다.

두 번째 줄에 행사값 $n_1, n_2, n_3, \cdots, n_M$이 공백으로 구분되어 정수로 주어진다.

세 번째 줄에 각 상품 종류에 대해, 당신이 가져가고 싶은 상품의 목표 개수 $a_1, a_2, a_3, \cdots, a_M$이 공백으로 구분되어 정수로 주어진다.

출력

첫 번째 줄에 $N+1$ 행사를 이용하여 각 상품 목표 개수를 모두 만족시키기 위해 구매해야 하는 1,ドル 2, 3, \cdots, M$번 상품에 대한 최소 구매 개수를 공백으로 구분하여 순서대로 모두 출력한다.

제한

• 1ドル \le M \le 100,000円$
• 1ドル \le n_i \le 100,000円$
• 0ドル \le a_i \le 10^9$

힌트