摘果实

题目描述

秋天,在一个果园里,有许多棵果树结满了很多果实。为了将它们摘下来,果园的阳阳请了一些的工人来摘果实。 不过,这些摘果实的工人采摘效率挺高的,在每一个单位时间内可以摘完一棵果树上的所有果实,但是那些工人很奇怪,他们摘果实时有些会看果树上有多少颗果实,且一旦果树上的果实的数目大于等于他们的限定值,则会拒绝摘那棵果树上的果实;另一些则是摘果实时看果树的高度,且一旦果树上的高度大于等于他们的限定值,则会拒绝摘那棵果树上的果实。 由于阳阳今年的订单量很好,有许多客户想订购他的水果,于是他想知道,若给出果树的果实数和高度、两种类型工人的人数与他们各自的限制值,最少可以花多少个单位时间。

输入输出格式

输入格式


在输入中,其中第一行有三个数字$a$ ,$b$ , $n$ ,第一个数字为第一种类型工人,即采摘果实时果树上的果实数目有限制的工人的数目,第二个数字为第二种类型工人,即采摘果实时果树的高度有限制的工人的数目,第三个数字为果树的数目。 后面 $a$ 行,每行一个数字,描述每个第一种类型的工人对果树上的果实数目的限制值。 再后面 $b$ 行,每行一个数字,描述每个第二种类型的工人对果树的高度限制值。 再后面 $n$ 行,每行两个数字,分别描述每一颗果树所含的果实的数目以及它们的高度。

输出格式


输出只有一个数字,即为摘果实所耗费的最少单位时间大小,若无法摘到果实,则输出“Impossible”。

输入输出样例

输入样例 #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

输出样例 #1

3

输入样例 #2

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

输出样例 #2

Impossible

说明

在 输入输出样例#1 中,有$a = 3$ 位第一种类型的工人,他们对的果树果实数目限制是$X = [6, 2, 9]$ ,$ B = 2$ 位第二种类型的工人,他们的果树高度限制是$Y = [4, 7]$ ,有$n = 10$ 棵果树,具体信息如下: ![](https://cdn.luogu.org/upload/pic/9894.png) 将这些果树都收拾好的最短时间是3个单位时间,方案如下: ![](https://cdn.luogu.org/upload/pic/9895.png) 而在 输入输出样例#2 中,有$a = 2$ 位第一种类型的工人,他们对的果树果实数目限制是$X = [2, 5] $,$b = 1 $位第二种类型的工人,他们的果树高度限制是$Y = [2]$ ,有$n = 3 $棵果树,具体信息如下: ![](https://cdn.luogu.org/upload/pic/9896.png) 没有任何工人愿意采摘果实数目为5且树木高度为3的果树(编号1),所以不可能所有的果树都被采摘。 ## 子任务 ![imagedda05b0d34bdb15f.png](https://www.z4a.net/images/2018/07/24/imagedda05b0d34bdb15f.png) ## 题解 https://www.luogu.org/discuss/show?postid=52662