题目描述

有$\red{n}$件工作要分配给$\red{n}$个人做。第$\red{i}$ 个人做第$\red{j}$ 件工作产生的效益为$\red{C_{ij}}$ 。试设计一个将 $\red{n}$件工作分配给$\red{n}$个人做的分配方案，使产生的总效益最大。

编程任务： 对于给定的$\red{n}$件工作和$\red{n}$个人，计算最优分配方案和最差分配方案。

输入格式

第$\red{1}$ 行有$\red{1}$ 个正整数$\red{n}$，表示有$\red{n}$件工作要分配 给$\red{n}$ 个人做。接下来的$\red{n}$ 行中，每行有$\red{n}$ 个整数$\red{C_{ij} ，1≤i≤n，1≤j≤n(n<=100)}$，表示第$\red{i}$ 个人做第$\red{j}$件工作产生的效益为$\red{C_{ij}}$。

输出格式

程序运行结束时，将计算出的最小总效益和最大总效益输出。

样例

输入样例

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

输出样例

5
14