Pro.ID21106 TitleFarmer Title链接http://10.20.2.8/oj/exercise/problem?problem_id=21106 AC0 Submit221 Ratio0.00% 时间&空间限制描述A farmer has a set of fields, each of which is surrounded by cypress trees. Also, the farmer has a set of strips of land, each of which has a row of cypress trees. In both fields and strips, between every two consecutive cypress trees is a single olive tree. All of the farmer's cypress trees either surround a field or are in a strip and all of the farmer's olive trees are between two consecutive cypress trees in a field or in a strip. One day the farmer became very ill and he felt that he was going to die. A few days before he passed away he called his eldest son and told him, "I give you any Q cypress trees of your choice and all the olive trees which are between any two consecutive cypress trees you have chosen." From each field and from each strip the son can pick any combination of cypress trees. Since the eldest son loves olives he wants to pick the Q cypress trees which will allow him to inherit as many olive trees as possible.
In Figure 1, assume that the son is given Q=17 cypress trees. To maximize his olive inheritance he should choose all the cypress trees in Field 1 and Field 2, inheriting 17 olive trees. You are to write a program which, given the information about the fields and the strips and the number of cypress trees the son can pick, determines the largest possible number of olive trees the son may inherit. 输入The first line contains first the integer Q: the number of cypress trees the son is to select; then the integer M, the number of fields; and then the integer K, the number of strips. The second line contains M integers N1, N2, ..., NM, : the numbers of cypress trees in fields. The third line contains K integers R1, R2, ..., RK: the numbers of cypress trees in strips. In all inputs, 0 ≤ Q ≤ 150000, 0 ≤ M ≤ 2000, 0 ≤ K ≤ 2000, 3 ≤ N1 ≤ 150, 3 ≤ N2 ≤ 150, ..., 3 ≤ NM ≤ 150, 2 ≤ R1 ≤ 150, 2 ≤ R2 ≤ 150, ..., 2 ≤ RK ≤ 150. The total number of cypress trees in the fields and strips is at least Q. 输出Description A farmer has a set of fields, each of which is surrounded by cypress trees. Also, the farmer has a set of strips of land, each of which has a row of cypress trees. In both fields and strips, between every two consecutive cypress trees is a single olive tree. All of the farmer's cypress trees either surround a field or are in a strip and all of the farmer's olive trees are between two consecutive cypress trees in a field or in a strip. One day the farmer became very ill and he felt that he was going to die. A few days before he passed away he called his eldest son and told him, "I give you any Q cypress trees of your choice and all the olive trees which are between any two consecutive cypress trees you have chosen." From each field and from each strip the son can pick any combination of cypress trees. Since the eldest son loves olives he wants to pick the Q cypress trees which will allow him to inherit as many olive trees as possible.
In Figure 1, assume that the son is given Q=17 cypress trees. To maximize his olive inheritance he should choose all the cypress trees in Field 1 and Field 2, inheriting 17 olive trees. You are to write a program which, given the information about the fields and the strips and the number of cypress trees the son can pick, determines the largest possible number of olive trees the son may inherit. Input The first line contains first the integer Q: the number of cypress trees the son is to select; then the integer M, the number of fields; and then the integer K, the number of strips. The second line contains M integers N1, N2, ..., NM, : the numbers of cypress trees in fields. The third line contains K integers R1, R2, ..., RK: the numbers of cypress trees in strips. In all inputs, 0 ≤ Q ≤ 150000, 0 ≤ M ≤ 2000, 0 ≤ K ≤ 2000, 3 ≤ N1 ≤ 150, 3 ≤ N2 ≤ 150, ..., 3 ≤ NM ≤ 150, 2 ≤ R1 ≤ 150, 2 ≤ R2 ≤ 150, ..., 2 ≤ RK ≤ 150. The total number of cypress trees in the fields and strips is at least Q. Output The output is to contain one line with one integer: the largest possible number of olive trees the son may inherit. Sample Input 5 Sample Output 17 Source 样例输入5 样例输出17 提示作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2024-9-21 17:30 , Processed in 0.016426 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
