Very Important People

View as PDF

Submit solution

Points: 0.91 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
C11 Contest Round 22 - Nguyễn Xuân Khánh
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Trong rạp chiếu phim có ~N~ ghế dành cho ~N~ vị khách.

Mỗi người lần lượt vào rạp xem phim và phải ngồi vào đúng chỗ của mình (người vào thứ ~i~ phải ngồi ghế thứ ~i)~.

Tuy nhiên, có một ông khách VIP vào đầu tiên và được giành lấy một ghế bất kì. Mỗi người tiếp theo khi vào rạp thì ý thức hơn nên sẽ ngồi vào đúng chỗ (nếu ghế của họ chưa có người ngồi). Nhưng nếu chỗ của họ đã bị lấy mất thì họ được quyền chọn ~1~ ghế khác bất kì.

Ta biết ~C[i~, ~j]~ là độ hài lòng của vị khách thứ ~i~ khi ngồi vào ghế thứ ~j~. Hãy tính giá trị lớn nhất có thể của tổng độ hài lòng của ~N~ vị khách.

Input

  • Dòng đầu tiên là số nguyên dương ~N~ ~(1 \le N \le 1000)~;
  • Dòng thứ ~i~ (trong ~N~ dòng tiếp theo) gồm ~N~ số nguyên. Số thứ ~j~ cho là giá trị ~C[i~, ~j]~ ~(|C[i, j]| \le 1\,000\,000\,000)~;

Output

  • Một số nguyên duy nhất là tổng lớn nhất có thể đạt được.

Sample Input

4
2 6 8 6 
5 0 6 7 
8 0 1 9 
2 7 2 4

Sample Output

24

Comments

Please read the guidelines before commenting.


There are no comments at the moment.