32143번 - 카드 게임 (Hard)

문제

당신은 카드 게임을 하고 있다.

상대의 체력은 $H$이며, 당신은 다양한 공격력을 가진 카드를 총 $N$개 가지고 있다. 만약 어떤 카드를 사용하여 공격하면, 상대의 체력은 그 카드의 공격력만큼 줄어든다. 체력이 0ドル$ 이하가 되면 죽는다.

당신은 패에 있는 카드를 아끼기 위해서 카드를 최대한 적게 써서 상대를 죽이려고 한다. 이때, 다양한 상황에 대비하기 위해서, $Q$개의 카드에 대하여 각 카드가 순서대로 추가되는 상황에 대해 이 문제를 풀려고 한다.

각 카드가 추가되었을 때 상대를 죽이기 위해 사용해야 하는 카드 개수의 최솟값을 구하거나, 죽이는 것이 불가능한지 판별하여라. 여기서 각 쿼리는 누적되며, 각 카드는 쿼리당 1번만 사용할 수 있다.

입력

첫 번째 줄에 $H$가 주어진다.

두 번째 줄에 $N$과 $Q$가 공백으로 구분되어 주어진다.

세 번째 줄에 처음 가지고 있는 카드들의 공격력을 나타내는 $N$개의 정수 $D_1, D_2, \cdots, D_N$가 공백으로 구분되어 주어진다.

네 번째 줄부터 $Q$개의 줄 중 $i$번째 줄에 $i$번째로 추가되는 카드의 공격력을 나타내는 정수 $x$가 주어진다.

출력

첫 번째 줄에 처음 가지고 있는 $N$개의 카드에 대해 상대를 죽이기 위해 사용하는 카드 개수의 최솟값을, 만약 죽이는 것이 불가능하다면 $-1$을 출력하여라.

두 번째 줄부터 $Q$개의 줄 중 $i$번째 줄에 $i$번째 카드를 추가한 후의 문제의 답을 첫 번째 줄과 같은 방법으로 출력하여라.

제한

• 1ドル \leq H \leq 10^9$
• 1ドル \leq N,Q \leq 300,000円$
• 1ドル \leq D_i \leq 10^9$
• 1ドル \leq x \leq 10^9$

힌트