Description

小W在八中开了一个兼职中心。

现在他手下有N个工人。每个工人有N个工作可以选择，于是每个人做每个工作的效率是不一样的。做为CEO的小W的任务就是给每个人分配一个工作，保证所有人效率之和是最大的。

N<=200

Format

Input

第一行给出数字N 接下来N行N列，代表每个人工作的效率。

Output

一个数字，代表最大效率之和

Samples

4
62 41 86 94
73 58 11 12
69 93 89 88
81 40 69 13

329