小塔是一位热爱美食的算法研究员，她正在研究如何为朋友们安排美食派对以获得最大的幸福感。她邀请了N位朋友来品尝M种不同的食物，并记录了每位朋友对每种食物的好感度ai,jai,j。
现在，小塔想要设计一个美食分配方案，使得总好感度最高，同时保证至少有一种食物被超过一半的朋友品尝过。你能帮助她解决这个问题吗？
给定N个人和M种食物，每个人对每种食物有一个好感度ai,jai,j。你需要找到一个分配方案，使得：
数学表达式为：最大化∑i=1Nai,ci∑i=1Nai,ci，其中cici表示第i个人选择的食物，且存在某个食物kk满足: ∑i=1N[ci=k]>⌊N/2⌋∑i=1N[ci=k]>⌊N/2⌋。其中 [a][a] 为艾佛森括号，若表达式aa为真则返回1，为假则返回0。
输入包含多组测试数据。第一行包含一个整数T，表示测试数据的组数。
对于每组测试数据：
数据范围：
2
5 3
1 2 3
4 5 6
7 8 9
10 11 12
13 14 15
3 2
200 100
400 300
500 60045
1200