Մատրիցային խաղ
Աննան և Բաբկենը խաղում են հետևյալ խաղը։ Նրանք ունեն NxN չափի վանդակավոր դաշտ, յուրաքանչյուր վանդակում գրված է մեկ բնական թիվ։ Առաջին խաղացողն ընտրում է ցանկացած տող, որում կա առնվազն մեկ բնական թիվ: Երկրորդ խաղացողն ընտրում է սյունակ և իր միավորներին գումարում է այդ տողի և սյունակի հատման վանդակում գրված թիվը, ապա այդ վանդակի թիվը ջնջում, փոխարենը զրո է գրում: Հաջորդ քայլին դերերը փոխվում են։ Այժմ երկրորդ խաղացողն ընտրում է տող, իսկ առաջին խաղացողը՝ սյունակ: Հետո նորից դերերը փոխում են, և այդպես շարունակ։
Խաղն ավարտվում է, երբ բոլոր վանդակներում զրոներ են գրված լինում: Խաղացողներից յուրաքանչյուրը կիրառում է այնպիսի մարտավարություն, որ հակառակորդի միավորը հնարավորինս փոքր լինի, իսկ իր միավորը՝ հնարավորինս մեծ։
Գրեք ծրագիր, որը կգտնի խաղի վերջում Աննայի կուտակած թվերի գումարը և Բաբկենի կուտակած թվերի գումարը, եթե Աննան սկսի խաղը:
Մուտքային տվյալներ
Առաջին տողը պարունակում է մեկ ամբողջ
N (1 ≤ N ≤ 500) թիվ՝ տախտակի չափը: Հաջորդ N տողերից յուրաքանչյուրը պարունակում է N հատ 100-ը չգերազանցող բնական թվեր։Ելքային տվյալներ
Պետք է արտածել երկու ամբողջ թվեր՝ Աննայի և Բաբկենի միավորները խաղի վերջում:
Օրինակ
Մուտք | Ելք |
2
1 2
3 4 | 4 6 |
3
1 2 3
4 5 6
7 8 9 | 21 24 |
Ենթախնդիրներ
- Ենթախնդիր 1 (30 միավոր)
Nը զույգ է
- Ենթախնդիր 2 (35 միավոր)
N ≤ 5
- Ենթախնդիր 3 (35 միավոր)
Nը կենտ է
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB