피로를 이겨내는 휴가

면접 대비

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

요약

시작 활력 D와 두 활동 목록이 주어질 때, 윌리엄이 정해진 우선순위 규칙대로 수행할 수 있는 활동의 총 개수를 구합니다.

난이도: 쉬움10점 중 3점
유형: 시뮬레이션, 투 포인터
정답자: 아직 제출이 없습니다

문제

윌리엄은 다가오는 휴가를 계획하고 있다. 여행 중에는 피로가 반복해서 문제가 된다. 활동을 몇 개 하고 나면 피로가 그가 감당할 수 있는 수준을 넘어서, 그날을 즐기지 못하는 날이 있다.

이번에 윌리엄은 관광 활동 하나하나가 자신의 컨디션에 주는 영향을 미리 따져 보기로 했다. 스포츠나 등산은 피곤해서 컨디션을 소모하고, 연극이나 뮤지컬은 기운을 나게 해서 컨디션을 회복시킨다.

자세히 말하면, 윌리엄은 컨디션 D 단위로 시작하고, 활동을 피로 활동 C개와 회복 활동 R개의 두 그룹으로 나눈다. 각 피로 활동은 필요한 컨디션이 정해져 있고, 수행하면 그만큼 컨디션을 소모한다. 각 회복 활동은 수행하면 일정량의 컨디션을 회복시킨다. 각 그룹의 활동은 그의 선호 순서대로 나열되어 있다. 두 그룹의 활동은 섞어서 수행할 수 있지만, 어느 그룹의 활동이든 그 그룹의 앞선 활동을 모두 마친 뒤에만 수행한다. 선호에 맞지 않기 때문이다.

다음 활동을 고를 때, 아직 하지 않은 피로 활동 중 첫 번째 것이 있고 컨디션이 충분하면 그 활동을 한다. 컨디션이 부족하면 아직 남아 있는 회복 활동 중 다음 것을 수행해 컨디션을 회복한다. 어느 시점에든 피로 활동이 남아 있지 않으면 남은 회복 활동을 모두 수행할 수 있다.

윌리엄이 수행할 수 있는 활동의 총 개수(피로 활동과 회복 활동을 모두 포함)를 구하라.

입력

첫 줄에 세 정수 D, C, R이 주어진다. 각각 초기 컨디션, 피로 활동의 수, 회복 활동의 수이다( $1 \le D \le 10^5$ , $1 \le C \le 10^4$ , $1 \le R \le 10^4$ ). 이어지는 C개의 줄에는 정수 $C_i$ ( $1 \le C_i \le 10^5$ )가 하나씩 주어지며, 선호 순서대로 i번째 피로 활동에 필요한 컨디션을 뜻한다. 이어지는 R개의 줄에는 정수 $R_i$ ( $1 \le R_i \le 10^5$ )가 하나씩 주어지며, 선호 순서대로 i번째 회복 활동이 회복시키는 컨디션을 뜻한다.

출력

윌리엄이 수행할 수 있는 활동의 총 개수(피로 활동과 회복 활동을 모두 포함)를 한 줄에 정수 하나로 출력한다.

예제3

예제 1
입력
```
40 3 3
30
20
10
5
5
5
```
예상 출력
```
5
```
예제 2
입력
```
40 2 2
60
80
5
10
```
예상 출력
```
2
```
예제 3
입력
```
100 3 1
60
60
50
10
```
예상 출력
```
2
```