5168: BZOJ1168:[Baltic2008]Gloves

Memory Limit:162 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

手套被放在了两个抽屉里, 所有的左手套放在左边的抽屉里, 所有的右手套放在右边的抽屉里.手套一共有N种颜色, 已知两个抽屉每种颜色的手套各有多少只, 如果随便在左边拿一只, 右边拿一只 很可能会造成拿到一只红色的左手套和一只蓝色右手套... 现想知道应该从左边的抽屉取出多少只左手套(设为x) 右边的抽屉取出多少只右手套(设为y), 满足至少可以找到一对匹配的手套(即颜色相同), 并且x + y最小 如果有多个(x, y)满足x + y最小, 你希望满足x尽可能的小不妨设 每个抽屉里每只手套被取出的概率是等价的.输入文件输入文件第一行中有一个正整数N,表示颜色的种数.第二行有N个非负整数, 表示左抽屉中每种颜色的左手套的个数.第三行有N个非负整数, 表示右抽屉中每种颜色的右手套的个数.输出文件你需要输出满足题目条件的(x, y).


输入格式

输入文件第一行中有一个正整数N,表示颜色的种数.第二行有N个非负整数, 表示左抽屉中每种颜色的左手套的个数.第三行有N个非负整数, 表示右抽屉中每种颜色的右手套的个数.


输出格式

输出满足题目条件的(x, y).


样例输入

4
0 7 1 6
1 5 0 6

样例输出

2 8

提示

100%的测试数据, N <= 20, 0 <= ai, bi <= 108.


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: