Mike has N vases standing in a row. Those vases are wonderful, but the whole row seems ugly. Because some vases are completely incompatible with the others. So, now he wants to reorder them in the way that row is as pretty as possible. Basically, only those vases which stand next to each other affect ugliness or beauty of the row. For each pair of vases you know the "ugliness" of this pair. Your task is to order vases in such a way that sum of uglinesses of all the adjacent pairs of vases is as little as possible. You cannot move the first or the last vase, only those which are between them. Input data specification: First line contains one number N. Then N lines follow, each contains N numbers. i-th number of j-th row says how ugly are i-th and j-th vases when i-th vase is to the right of the j-th one. First vase is the leftmost one, and the N-th vase is the rightmost one. Output data specification: Output the only number: minimal possible ugliness of the row after reordering all the vases except the first one and the last one. Sample input: 4 0 4 1 3 5 0 3 2 7 2 0 7 7 8 6 0 Sample output: 5 Sample description: There are only two reordegings: 1 2 3 4 (which means not to move anything) and 1 3 2 4, which can be achieved by swapping second and third vases. In the first case ugliness is 4 + 3 + 7 = 14, in the second case it is 1 + 2 + 2 = 5, which is less.