Overload Prevention

Interview

Time limit1sMemory limit1024 MB

Summary

Given power strips with their socket counts, K wall outlets, and M devices with maximum strip-depth limits, find the most devices that can receive power.

Level: Medium5 of 10
Topics: Greedy, Sorting, Simulation
Solved: No attempts yet

Problem

Eunha moved into a new home and brought $M$ electronic devices and $N$ power strips. The power strips have unlimited length.

The new home has $K$ wall outlets ( $K \le M$ ). Eunha wants to connect the electronic devices to power using the power strips. A power strip may be plugged into a socket of another power strip. However, some devices use a lot of power. If power reaches such a device through more than a set number of power strips, the device may overload and catch fire.

Under these conditions, can Eunha connect as many devices to power as possible?

Input

The first line contains three integers $N$ , $K$ , and $M$ , the number of power strips, the number of wall outlets, and the number of electronic devices, separated by spaces. ( $1 \le N \le 200\,000$ , $1 \le K \le M \le 200\,000$ )

The second line contains $N$ integers $A_1, \cdots, A_N$ , the number of sockets on each power strip, separated by spaces. ( $1 \le A_i \le 200\,000$ )

The third line contains $M$ integers $D_1, \cdots, D_M$ , separated by spaces. $D_i$ is the maximum number of power strips that the current may pass through from a wall outlet to device $i$ . The number of power strips on the path to a device is the number of power strips the current passes through before reaching it. ( $0 \le D_i \le 200\,000$ )

A device with $D_i = 0$ can only be connected directly to a wall outlet.

Output

Print the number of devices that receive power when as many devices as possible are powered.

Examples2

Example 1
Input
```
3 1 10
1 2 3
3 1 4 1 5 9 2 6 5 3
```
Expected output
```
4
```
Example 2
Input
```
2 2 6
2 4
2 4 0 2 0 3
```
Expected output
```
5
```