U595854 三角洲难题

众所周知，**三角洲行动**是一款火爆的搜打撤类型的fps游戏，lk最近就沉迷上了这个游戏，但是一向数学不太好的lk却发现了一个难题： 在这个游戏中有很多不同价值的物品，如**水泥**（尺寸为$2 \times 3$但是它的价值却只有可怜的 $52000$），而**非洲之心**(尺寸仅为 $1 \times 1$,价值却高达 $13825367$)。 那么，如何合理规划背包空间才能使带出物品的价值最高呢？ lk想请你写一个程序帮他解决这个问题。

输入lk当前的背包格式，和 $T$ 个物品的价值、长和宽，现在请你求出lk所能带走的**最大**价值是多少。**(物品不能重复放置)**

首先，输入 $m$ 和 $n$ ，分别表示背包的行和列能存贮物品的大小。 其次，一个$m \times n$的字符矩阵，其中 $ * $ 表示这一格不能放任何物品， $ - $ 表示这一格可以放物品。 然后，输入物品个数 $T$。 接下来共有 $T$ 行，第 $i$ 行为第 $i$ 个物品的价值 $w$ ，长 $l$ ，宽 $s$（长 $l$ 和宽 $s$ 为物品占据的行数和列数,**可以旋转**，**不保证$l>s$**）。

一个整数，表示lk能装走的最大价值。

对于100%的测试点数据： 保证 $2 ≤ T ≤ 20$ , $0 ≤ m, n ≤ 5$ ， $0 ≤ w ≤ 2147483647$ , $1 ≤ s ≤ l ≤ 100$ ### 目前数据较水，欢迎投稿Hack数据！