Background

在工厂里，如果每道工序让不同的工人来做，所要花费的时间往往不一样。精明的老板为了提高效率，总是把生产某一产品所需要的N道工序进行最佳搭配，使生产某一产品所花费的总时间最少。现在就给出N个工人分别做N道工序所要花费的时间，请你来计算一下,如果N个工人每人做N道工序中其中的一道，那么生产某一产品（即完成所有N道工序）所要花费的最少时间是多少。

Input

输入第1行有1个整数N(1≤N≤20)，表示有N个工人。接下来的N行，每行N个数，表示该工人完成各道工序所要花费的时间。

Output

输出共一行，即生产某一产品所要花费的最少时间。

Samples

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

6