U602687 [YHOI:YSJ]Ysj喜欢打三角洲

### 八宝粥是一款由槟榔地下开发的一款多人FPS枪战游戏 在此声明本题目与琳琅天上团队所开发项目《三角洲行动》无关 本题由Ysj中午普坝黑卡出大红有感而来 祝三角洲日活跃用户达2e7位 

## 进入正题 神秘爆零人（~~Ysj~~）发现八宝粥的背包空间是有限的，然而大坝的每种资源都是无限的（物品也是）。 于是他便在想该怎么撤离才能把撤离收入变得更加的高（~~毕竟还要去猛攻航天~~）。 面前，allornoting（下面简称all）有$T$种物品，价值分别为$a_i$，占格分别为$b_i*c_i$，其搜索时间为$d_i$。 all目前有一个空间为$n*m$格的背包和长度为$t$的总搜索时间。 ## 重点 背包是有分隔的。比如4*6背包格子可以有以下分布： ### 1. ``` 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 3 3 2 2 3 3 ``` ### 2. ``` 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ``` 其中不同的数代表处于不同的空间。 详情可见[阿萨拉突击背包](https://cdn.luogu.com.cn/upload/image_hosting/emklsmcc.png)（第一种分布格式），[这中的D2战术背包](https://cdn.luogu.com.cn/upload/image_hosting/r5mkmq50.png)（第二种分布格式） 现在求该在搜索时间内怎么挑选物品既使背包能装得下， 又可以带出的最高价值 [](偷偷告诉你输出样例即可得满分)

第一行，输入两个整数$T$和$t$，表示物品种数和总搜索时间。 下面$T$行，分别输入$a_i$，$b_i$，$c_i$，$d_i$。 下面一行输入背包（矩阵）大小，即，$n$，$m$。 下面输入一个大小为$n\times m$的矩阵。

输出一行一个整数，代表最高价值。

对于30pts，背包不分格，且$b_i$,$n$全部为1。（提示：可以用二维背包版子来写） 对于100pts，背包不分格。 **【数据范围】** 对于 $100 \%$ 的数据，保证$1 \le T \le 100$，$1 \le t \le 100$，$1 \le n \le 8$，$1 \le m \le 8$。 其他数据保证在 $int$ 范围之内。