Tian Ji, one of the military generals of the Qi state during 4th century BC, liked playing horse racing and once he was invited to participate in a horse-racing event hosted by King Wei of Qi. The e
Tian Ji, one of the military generals of the Qi state during 4th century BC, liked playing horse racing and once he was invited to participate in a horse-racing event hosted by King Wei of Qi. The event lasted for k days and both Tian Ji and King Wei of Qi were all well-prepared for the coming event. Now Tian Ji had n horses with speeds of a1, a2, ..., an and King Wei of Qi had n horses with speeds of b1, b2, ..., bn. In each day, there were n matches where both of them used one of their own horses. Since the horses would be tired after the match, each horse could be used only once in each day. The excitement of each match was the sum of the speeds of the two horses used in this match. In order to make the event more exciting, the matches in any two different days couldn't be exactly the same. That is to say, In any two different days, there was at least one horse that had different opponents in the two days. You, the brilliant in the 21st century AD, need to calculate the maximum possible value of the minimum of the excitement in the k×n matches during the k-day event. 齐国的大将田忌很喜欢赛马，有一回他被齐威王请来赛 k 天马。经过精心的准备，现在田忌有 n 匹速度分别为 a1, a2, ..., an 的马，齐威王则有 n 匹速度分别为 b1, b2, ..., bn 的马。每天要进行 n 场比赛，每场比赛田忌和齐威王分别会派出一匹马，每匹马每天只能上场一次，每场比赛的精彩程度是上场的两匹马的速度之和。为了让比赛更精彩，任意不同的两天里进行的比赛不能完全相同，也就是说，对于任意不同的两天，存在至少一匹马在这两天比赛的对手不同。你需要计算出这 k 天总计 k×n 场比赛中精彩程度最小值的最大可能值。
