题目描述

现在由 n 个人去完成 n 项任务（人的编号和任务的编号分别为 1 到 n ），每人做且只能做一项任务。现给程每个人完成各项任务所需要的时间，请你给出一个分配方案要求每个人完成任务所需的时间总和最小。

输入格式

第一行包括一个正整数 n ，接下来的 n 行，每行均有 n 个数，第 i+1 行的第 j 个数表示编号为 i 的人完成任务 j 所需的时间。

输出格式

一个数，表示最佳方案中 n 个人完成任务的时间总和。

样例

输入

5
13 11 10 4 7
13 10 10 8 5
5 9 7 7 4
15 12 10 11 5
10 11 8 8 4

输出

32

提示

数据范围： 1 < n <12 ,每个人任意一项任务的时间均不超过100。