Huy làm việc ở một kho hàng lớn. Kho hàng được mô tả bằng một ma trận N * N, ở ô tại hàng thứ i cột thứ j chứa khối hàng nặng a[i][j] kg.
Theo Huy, kho hàng sẽ sạch sẽ nếu kho hàng chứa hàng theo đúng mô hình là:

• Các ô nằm ở hàng thứ i của ma trận có đúng i khối hàng, hàng trên cùng của ma trận là hàng thứ 1.
• Ngoài những khối hàng để lại để làm cho kho sạch sẽ, Ucoder sẽ vứt tất cả các khối hàng còn lại đi.
• Huy muốn nhờ bạn tính tổng khối lượng nhỏ nhất có thể của các khối hàng để lại theo đúng mong muốn của Huy.

Mô tả đầu vào

• Dòng đầu chứa số N.
• N dòng tiếp theo, mỗi dòng chứa N số, là miêu tả kho hàng.

Ràng buộc

• 0 < N ≤ 100
• 0 < a[i][j] ≤ \(10^9\)

Mô tả đầu ra

Số duy nhất là đáp án bài toán.

3
5 2 4
3 6 7
10 5 10

36

4
45 8 3 1
1 10 5 67
4 4 3 18
10 4 7 12

51