积木堆砌的城堡

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/32768 K (Java/Others)

Description

一天,小希用积木搭了个城堡,并且照了正面和侧面的照片(前视图和右视图)给Gardon看,让Gardon猜猜她究竟用了多少块积木;Gardon发现从这两张照片上只能看出每一列上最高的地方有多高,但是无法推测出具体的形状(见图1、2),但是好在小希给了Gardon多次机会,所以Gardon只需要知道大概的范围就可以采用“二分查找”法来计算正确的结果。现在Gardon请你帮忙,根据这两张图,计算下最少和最多分别可能是多少块积木组成的,让他可以尽快的回答出小希的问题。

Input

输入可能包含多组数据。每组数据的第一行分别有两个数:W和L(0<W,L<=100000),分别表示了该城堡前视图和右视图的宽度,接下来的W行,每行有一个数,第i行表示前视图中第i个位置的高度。同样,接下来的L行表示了该城堡的右视图,每行的一个数字表示了右视图对应位置的高度。
已知城堡最高不会超过5000个积木的高度。

Output

对于每组数据,如果该城堡可能存在,输出两个数M和N(M,N<=10^14),表示最少可能的积木数和最多可能的积木数。如果该城堡不可能存在,输出"No solution."
注意积木不能悬空摆放。

Sample Input

4 3 1 3 4 2 1 4 2

Sample Output

10 21

Hint

lxj

Source

HDU 2006-4 Programming Contest

提交代码