题目描述
在每一个角落都被探索完毕的世界，为II一残留的秘境——大洞穴“阿比斯”。不知道延续到何方，深不见底的巨大纵向洞穴们，栖息着奇妙奇怪的生物们，沉眠着现在的人类无法制造的贵重遗物。
莉可，住在大洞穴之街“奥斯”，的孤儿院。她的母亲，是被称为“歼灭卿”的探窟加莱莎。莉可的愿望就是成为母亲一样强大的白笛。
居住在孤儿院的孩子们时常在深渊第一层收集遗物。这一天莉可被分配到了n*n的地，并且每一块地中遗物的价值是已知的。
莉可一共有n个收集遗物的机器。莉可一开始可以把这n个机器放在n个固定的地方。每个机器在收集这块地中的遗物的同时，可以监视它所在的一行和一列的所在地区。为了防止在收集过程中突然被深渊的怪物袭击，每个格子都有至少要被一个机器监视到，同时莉可希望收集到遗物的总价值尽可能大。
输入格式
第一行一个整数n.
接下来一个n*n的矩阵，描述每块地中遗物的价值。
输出格式
第一行输出一个整数，描述最大的收集到的遗物总价值。
接下来n行，每行2个整数x,y，描述一个机器的位置。如果有多种方案，输出任意一种即可。
样例输入
3
1 2 3
1 3 2
3 2 1
样例输出
9
1 3
2 2
3 1
数据范围
对于30%的数据，n<=5;
对于100%的数据，n<=1000,|a[i][j]|<=1000