一道算法题 k sum

Emily_Du

给定k个整数数列，每组恰好n个，求从每组中选出一个数，它们的和大于m的方案数。
输入
第一行给出n, m, k三个整数。
* n$ K; T# g5 n" w" s/ w& m0 i( D接下来k行，每行n个整数，表示这个数列中的所有元素。数列中每个元素为不超过10^7的正整数。
, o3 o. F/ L% ^' T! A% h输出
输出仅包括一行，即所求的方案数。
# F6 b% s; u9 @- O+ {样例输入
* i9 G" y! @  a3 10 2
+ K* L8 A' G, R& d4 6 8
5 2 5
样例输出
9 m7 @% }& i1 [6 g/ h4
Hint
' }# _% X% ?- I& U  v- c, b" @- ?数据范围
0 c" a9 o6 l2 Z$ n6 t. }* H对于30%的数据，1 <= n <= 10
对于100%的数据，1 <= n <= 100, 1 <= m < 2^31, 1 <= k <= 6。
$ J5 m3 h3 k6 v% X6 v

* o+ n7 a+ A6 p$ r1 t6 M* S1 d8 v我的思路是，考虑对每个数组先降序排序，然后求每个组合的值是否大于m，这样的话复杂度会比较高，最差情况下是6^100.
或者用动态规划方法，但不知道转移方程怎么写，求大神指点
8 T4 ?& ~  D% b
; m' H% o/ ^3 x% u- Y

lshqcable605

6666666666666

lshqcable605

8888888888888888
) ^& t3 L- Q+ f% j4 ~% N; g: R5 ^$ S1 K