Անկյունագծային գումար
Քառակուսի մատրիցի անկյունագծային գումար կանվանենք գլխավոր և երկրորդական անկյունագծերի տարրերի գումարը։
Տրված է
N × N չափի ամբողջ թվերից կազմած քառակուսի մատրից։ Հարկավոր է հաշվել այդ մատրիցի մեջ ընկած ամենամեծ անկյունագծային գումար ունեցող ենթամատրիցը։ Պետք է տպել այդ գումարը։Մուտքային տվյալներ
Առաջին տողում տրված է մատրիցի
N (1 ≤ N ≤ 400) չափը։ Հաջորդ N տողերից յուրաքանչյուրում տրված են [-10000, 10000] միջակայքի N ամբողջ թվեր։Ելքային տվյալներ
Պետք է արտածել մեկ թիվ՝ մեծագույն անկյունագծային գումարը։
Օրինակ
Մուտք. | Ելք. |
2
3 -1
4 6 | 12 |
4
0 -1 -2 -13
5 0 6 -2
0 -1 0 -1
0 0 7 0 | 17 |
Աղբյուրը՝ Հանրապետական 2021
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB