Fatigue-Fighting Vacation

Interview

Time limit0.5sMemory limit1024 MB

Summary

Given starting disposition D and two ordered activity lists, count how many activities William can perform under his choose-tiring-first rule.

Level: Easy3 of 10
Topics: Simulation, Two pointers
Solved: No attempts yet

Problem

William is planning his upcoming vacation. Fatigue is a recurring problem for him on trips. Some days, after several activities, his fatigue grows beyond what he can handle, and he does not enjoy the day.

This time William estimates the effect of each tourism activity on his disposition. Sports and hikes are tiring and consume his disposition, while theatre plays and musicals are invigorating and restore it.

More precisely, William starts with D units of disposition and splits his activities into two groups: C tiring activities and R invigorating activities. Each tiring activity requires a certain amount of disposition and consumes that amount when performed. Each invigorating activity restores a certain amount when performed. The activities in each group are ordered by his preference. Activities from both groups may be interleaved, but he never performs an activity from a group unless he has already performed all earlier activities in that group.

When choosing his next activity, he takes the first untaken tiring activity if he has enough disposition to do it. Otherwise he performs the next untaken invigorating activity, if one remains, which restores disposition. If no tiring activities remain at any point, he can perform all the remaining invigorating activities.

Find how many activities (both tiring and invigorating) he will be able to perform.

Input

The first line contains three integers D, C, and R, the initial disposition, the number of tiring activities, and the number of invigorating activities ( $1 \le D \le 10^5$ , $1 \le C \le 10^4$ , $1 \le R \le 10^4$ ). Each of the next C lines contains an integer $C_i$ ( $1 \le C_i \le 10^5$ ), the disposition required by the i-th tiring activity in order of preference. Each of the next R lines contains an integer $R_i$ ( $1 \le R_i \le 10^5$ ), the disposition provided by the i-th invigorating activity in order of preference.

Output

Print a single integer, the total number of activities (both tiring and invigorating) that William can perform.

Examples3

Example 1
Input
```
40 3 3
30
20
10
5
5
5
```
Expected output
```
5
```
Example 2
Input
```
40 2 2
60
80
5
10
```
Expected output
```
2
```
Example 3
Input
```
100 3 1
60
60
50
10
```
Expected output
```
2
```