一道算法题 k sum

Emily_Du

给定k个整数数列，每组恰好n个，求从每组中选出一个数，它们的和大于m的方案数。
输入
第一行给出n, m, k三个整数。
$ C, O% n- [+ w/ g接下来k行，每行n个整数，表示这个数列中的所有元素。数列中每个元素为不超过10^7的正整数。
输出
5 U* o' t2 i7 c输出仅包括一行，即所求的方案数。
, Z7 [' f  ]: ?+ B, X8 |- F样例输入
3 10 2
4 6 8
5 2 5
样例输出
7 ?  f! k" j6 n5 b( z, J8 ?4
Hint
9 G( ~- ?) T5 z' L/ g数据范围
7 S% F' l7 b" R& ^) t9 Y对于30%的数据，1 <= n <= 10
# Z) i; g( c) D' _: B) `对于100%的数据，1 <= n <= 100, 1 <= m < 2^31, 1 <= k <= 6。
/ k, W& U9 V. i" t6 x) f, D  t

我的思路是，考虑对每个数组先降序排序，然后求每个组合的值是否大于m，这样的话复杂度会比较高，最差情况下是6^100.
* {0 y# R- i3 R; t$ b. N: n或者用动态规划方法，但不知道转移方程怎么写，求大神指点

- W+ V4 _  r! ?6 T# M

lshqcable605

6666666666666
2 Q, H: L, Q8 T/ p: w

lshqcable605

8888888888888888
( U$ R8 H' ?; N% `