### IOI '13 - Brisbane, Australia

## Robots

Marita's little brother has left toys all over the living room floor! Fortunately, Marita has developed special robots to clean up the toys. She needs your help to determine which robots should pick up which toys.

There are T toys, each with an integer weight W[i] and an integer size S[i]. Robots come in two kinds: *weak* and *small*.

- There are A weak robots. Each weak robot has a weight limit X[i], and can carry any toy of weight strictly less than X[i]. The size of the toy does not matter.
- There are B small robots. Each small robot has a size limit Y[i], and can carry any toy of size strictly less than Y[i]. The weight of the toy does not matter.

Each of Marita's robots takes one minute to put each toy away. Different robots can put away different toys at the same time.

Your task is to determine whether Marita's robots can put all the toys away, and if so, the shortest time in which they can do this.

As a first example, suppose there are A = 3 weak robots with weight limits X = [6, 2, 9], B = 2 small robots with size limits Y = [4, 7], and T = 10 toys as follows:

Toy Number | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|

Weight | 4 | 8 | 2 | 7 | 1 | 5 | 3 | 8 | 7 | 10 |

Size | 6 | 5 | 3 | 9 | 8 | 1 | 3 | 7 | 6 | 5 |

The shortest time to put all the toys away is three minutes:

Weak robot 0 | Weak robot 1 | Weak robot 2 | Small robot 0 | Small robot 1 | |
---|---|---|---|---|---|

First minute | Toy 0 | Toy 4 | Toy 1 | Toy 6 | Toy 2 |

Second minute | Toy 5 | Toy 3 | Toy 8 | ||

Third minute | Toy 7 | Toy 9 |

As a second example, suppose there are A = 2 weak robots with weight limits X = [2, 5], B = 1 small robot with size limit Y = [2], and T = 3 toys as follows:

Toy number | 0 | 1 | 2 |
---|---|---|---|

Weight | 3 | 5 | 2 |

Size | 1 | 3 | 2 |

No robot can pick up the toy of weight 5 and size 3, and so it is impossible for the robots to put all of the toys away.

### Input Format

The input will be in the following format:

- Line 1 will contain three integers A, B (0 ≤ A, B ≤ 50,000, and 1 ≤ A + B) and T (1 ≤ T ≤ 1,000,000), respectively representing the number of weak robots, the number of small robots, and the number of toys.
- Line 2 will contain A integers, the values of X[i] (1 ≤ X[i] ≤ 2,000,000,000), that specify the weight limit for each weak robot.
- Line 3 will contain B integers, the values of Y[i] (1 ≤ Y[i] ≤ 2,000,000,000), that specify the size limit of each small robot.
- The next T lines will each contain two integers W[i] and S[i] (1 ≤ W[i], S[i] ≤ 2,000,000,000), the weight and size of each toy, respectively.

If A = 0 or B = 0, then the corresponding line (line 2 or line 3) should be empty.

### Output Format

The output should contain one integer - the smallest number of minutes required to put all of the toys away, or -1 if this is not possible.

### Sample Input 1

3 2 10 6 2 9 4 7 4 6 8 5 2 3 7 9 1 8 5 1 3 3 8 7 7 6 10 5

### Sample Output 1

3

### Sample Input 2

2 1 3 2 5 2 3 1 5 3 2 2

### Sample Output 2

-1

### Description of Samples

The first sample input describes the first example above, which is summarized as follows:

Parameter | Value |
---|---|

A | 3 |

B | 2 |

T | 10 |

X | [6, 2, 9] |

Y | [4, 7] |

W | [4, 8, 2, 7, 1, 5, 3, 8, 7, 10] |

S | [6, 5, 3, 9, 8, 1, 3, 7, 6, 5] |

Output | 3 |

The second sample input describes the second example above, which is summarized as follows:

Parameter | Value |
---|---|

A | 2 |

B | 1 |

T | 3 |

X | [2, 5] |

Y | [2] |

W | [3, 5, 2] |

S | [1, 3, 2] |

Output | -1 |

### Subtasks

Subtask | Percent of Points | Additional Input Constraints |
---|---|---|

1 | 14 | T = 2 and A + B = 2 (exactly two toys and two robots) |

2 | 14 | B = 0 (all robots are weak) |

3 | 25 | T ≤ 50 and A + B ≤ 50 |

4 | 37 | T ≤ 10,000 and A + B ≤ 1,000 |

5 | 10 | (None) |

All Submissions

Best Solutions

**Point Value:** 20 (partial)

**Time Limit:** 4.00s

**Memory Limit:** 64M

**Added:** Jul 28, 2013

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

mahmoudhassanon Jul 17, 2016 - 8:42:46 pm UTC Weak Test DataBon Jun 26, 2017 - 9:50:46 pm UTC Re: Weak Test Datamanolismion May 16, 2015 - 1:21:15 pm UTC TLEmanolismion Mar 25, 2015 - 11:16:21 am UTC Wrong AnswerCan somebody help me?

jargonon Mar 25, 2015 - 9:06:14 pm UTC Re: Wrong AnswerSince the IOI publishes its test data, you can always go look it up yourself.

Kiokon Aug 29, 2013 - 5:48:04 pm UTC Runtime ErrorBut I got 100/100 points...

Is there any input (A+B=0) ?

Alexon Aug 29, 2013 - 6:00:24 pm UTC Re: Runtime Error