思路：动态规划

背包的变种问题。

定义$f[j][t]$表示购买前$j$列的$j$种气球，花费为$t$的方法有多少种。

那么有状态转移方程$f[j][t]=f[j][t]+f[j-1][t-a[i][j]]$，其中，$a[i][j]$为第$i$行第$j$列气球的价格。其意义为：当前$j$列花费为$t$时，枚举当前气球$a[i][j]$，如果购买当前气球，那么会为$f[j][t]$贡献$f[j-1][t-a[i][j]]$（第$j$列买$a[i][j]$花费为$t$，那么第$j-1$列花费为$t-a[i][j]$）。

代码

题目描述

小红所在的实验室出了重大科研成果，实验室准备庆祝一下，派小红去买气球装饰场地。

小红走到商店，发现一共有四种颜色的气球：红、黄、蓝、绿。突然他又发现，不同货架上的气球，即使是同种颜色，也会有不同的价格。

喜欢思考的小红突然想知道，要花光手上的1000元去买气球，有多少种方法？

输入描述

第一行为一个整数$N \leq 1000$，代表商店里的货架数量

接下来$N$行，每行4个正整数，分别表示四种气球的颜色(红、黄、蓝、绿)，每个数不超过$10000$

输出描述

一个正整数，代表方法数。

样例

输入

2
250 250 250 250
150 250 450 150

输出

4

提示

有如下4种选择

$1，1，1，1$

$1，2，1，1$

$2，2，2，2$

$2，1，2，2$