UOJ Logo

NOI.AC

1S 512MB

#1635. 寻宝游戏

Statistics

题目描述

stjean在玩一个寻宝游戏,他在一个n×m的地图上,起始在(1,1),现在他想去(n, m)
这个地图上每个格子都会有一个价值 a_ij 的宝物,每次到达一个格子,他会捡起宝物
现在他想知道,如果每次只能 由(x, y) -> (x, y + 1) 或者 (x, y) -> (x + 1, y)
当他走到(n, m)时,手中宝物总价值为k的方案数有多少种?

文件输入

第一行n和m和k
下面n行,每行m个数

文件输出

输出方案数

输入样例

2  2  6    
2  1
1  3

输出样例

2

数据规模

对于所有的数据,k在long long 范围内
对于20%的数据,n,m <= 3    a_ij <= 10
对于20%的数据,n,m <= 12   a_ij <= 1000
对于20%的数据,n,m <= 20   a_ij <= 10
对于40%的数据,n,m <= 20  a_ij <= 1000000000