카드 게임 (Hard)

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

요약

카드가 하나씩 추가될 때마다 공격력 합이 H 이상이 되는 최소 카드 수를 구하고, 불가능하면 -1을 출력한다.

문제

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

상대의 체력은 $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$ 번째 카드를 추가한 후의 문제의 답을 첫 번째 줄과 같은 방법으로 출력하여라.