103960

## problem 一只青蛙，他会跳，现在要从 $1$ 跳到 $n$。跳一次有 $m$ 种跳法，假设现在在 $x$，那么第 $i$ 次可以从 $x$ 跳到 $x+d_i$，同时消耗 $p_j$ 的能量。问你有多少种跳的方案使得消耗能量不超过 $k$。$n\leq 10^9,m\leq 10^5,1 ......