该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

数据已加强

题目背景

有个好心的dalao帮助WDG出题了，于是WDG就开始玩游戏了。

题目描述

WDG遇到了$n$个敌人，每个敌人都会释放$m$个技能，第$i$个敌人的第$j$个技能具有$A_{i,j}$点威力。

幸运的是，WDG有一个威力为$X$的群攻技能，这个技能可以破坏所有敌人一定数量的技能，只要这个技能的威力大于敌人对应技能的威力

这个技能有两种模式，当选定模式后，对于每一个敌人，都会运用这一种模式：

• 清算模式：对于每个敌人，如果其威力大于这个敌人的所有技能威力和（$X>\sum ^{j = 1}_m A_{i,j}$），则可以直接破坏这个敌人的全部技能。
• 交锋模式：给定一个正整数$t$，对于每个敌人，如果其威力大于这个敌人的第$t(t \leq m)$个技能的威力，则可以破坏这个敌人的第$t$个技能。

WDG十分贪婪，选择了清算模式，结果没有破坏任何一个技能，因此失败了。

WDG很伤心，不仅要出题，连玩游戏都被敌人随便打。

Harun想帮助WDG，于是他提出了一个问题：有$Q$次询问，每次询问给出WDG群攻技能的威力$X$和指向目标值$t$，对于这次查询，是选择清算模式破坏敌人技能的总威力和大，还是选择交锋模式破坏敌人技能的总威力和大？

输入格式

第一行输入三个数，分别是$n,m,q$

接下来有$n$行，每行有$m$个整数，第$i$行第$j$列元素为$A_{i,j}$

接下来有$Q$行，每行有2个正整数，为$X$和$t$

输出格式

输出$Q$行，每行输出两种模式下破坏敌人技能的总威力和的最大值

3 3 5
1 2 3
2 2 1
2 4 3
3 1
3 2
5 3
7 2
1 3

5
4
7
11
0

解释

第一次询问，选择清算模式，无法摧毁任何一个技能，选择交锋模式，可以摧毁所有敌人的第一个技能，威力总和为$1+2+2=5$

第四次询问，选择清算模式，可以摧毁$1,2$敌人的所有技能，威力总和为$1+2+3+2+2+1=11$选择交锋，可以摧毁所有敌人的第三个技能，威力总和为$2 + 2 + 4=8$，显然选择清算

第五次询问，怎么选择都不能摧毁任何一个技能，威力总和为$0$

提示

【数据范围】

对于$20\%$的数据，$n\times m \le 1000, Q \leq 1000$

另有$30\%$的数据，$n,m$中有一个数为$1$

另有$20\%$的数据，$A_{i,j} \leq 1$

另有$20\%$的数据，$t = 1$

对于$100\%$的数据，$t\leq m,n\times m \le 10^6 , A_{i,j} \leq 1000,Q\leq 10^5$