카드 게임 (Hard)

면접 대비

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

요약

체력 H와 공격 값 목록이 주어질 때, 카드를 하나씩 추가하면서 공격 합이 H 이상이 되는 최소 카드 수를 구하거나 불가능하면 -1을 구합니다.

난이도: 보통10점 중 5점
유형: 그리디, 이분 탐색, 세그먼트 트리
정답자: 아직 제출이 없습니다

문제

당신은 카드 게임을 하고 있다. 상대의 체력은 $H$ 이며, 당신은 공격력이 제각각인 카드를 $N$ 개 가지고 있다. 카드를 사용해 공격하면 상대의 체력은 그 카드의 공격력만큼 줄어든다. 체력이 $0$ 이하가 되면 상대는 죽는다.

패에 있는 카드를 아끼려고, 상대를 죽일 때 카드를 최대한 적게 쓰려고 한다. 다양한 상황에 대비하기 위해 $Q$ 개의 카드를 순서대로 추가하면서 매번 이 문제를 푼다. 카드가 추가될 때마다 상대를 죽이는 데 필요한 카드 개수의 최솟값을 구하거나, 죽이는 것이 불가능한지 판별하여라. 각 쿼리는 누적되며, 각 카드는 쿼리당 한 번만 사용할 수 있다.

입력

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

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

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

네 번째 줄부터 $Q$ 개의 줄이 주어지며, $i$ 번째 줄에는 $i$ 번째로 추가되는 카드의 공격력 $x$ 가 주어진다.

출력

첫 번째 줄에 처음 가지고 있는 $N$ 개의 카드로 상대를 죽이는 데 사용하는 카드 개수의 최솟값을 출력한다. 죽이는 것이 불가능하면 $-1$ 을 출력한다.

두 번째 줄부터 $Q$ 개의 줄에 걸쳐, $i$ 번째 줄에는 $i$ 번째 카드를 추가한 후의 답을 첫 번째 줄과 같은 방법으로 출력한다.

제한

$1 \leq H \leq 10^9$ \n- $1 \leq N,Q \leq 300\,000$ \n- $1 \leq D_i \leq 10^9$ \n- $1 \leq x \leq 10^9$

예제1

예제 1
입력
```
10
2 3
4 3
2
2
7
```
예상 출력
```
-1
-1
4
2
```