1372: ShacozzZ的山洞探险

ShacozzZ某一天来到了一个山洞，山洞的构造可以抽象成一个三角形的 $n$ 层数塔（第 $i$ 行有 $i$ 个房间），每一个房间都有一个宝物，第 $i$ 层的第 $j$ 个房间内的宝物价值为 $v_{i,j}$ ，宝物的重量为 $w_{i,j}$ 。

ShacozzZ现在在数塔的最顶层。每一次ShacozzZ可以向下走或者向右下走，即位置由 $(i,j)$ 变为 $(i+1,j)$ 或者 $(i+1,j+1)$。

而ShacozzZ的背包最多只能装 $m$ 重量的宝物，请问ShacozzZ最多能带走多少价值的宝物？

第一行包含两个整数 $n,m(1 \leq n,m \leq 200)$ 代表山洞的层数以及ShacozzZ的背包的容量。

接下来 $n$ 行，第 $i$ 行包含 $i$ 个整数 $v_{i,j}(1 \leq v_{i,j} \leq 200)$，代表第 $i$ 层第 $j$ 个房间的宝物的价值。

接下来 $n$ 行，第 $i$ 行包含 $i$ 个整数 $w_{i,j}(1 \leq w_{i,j} \leq 200)$，代表第 $i$ 层第 $j$ 个房间的宝物的重量。

输出包含一个整数 $V$ ，代表ShacozzZ能收获的最大价值。

3 4
8
5 100
5 1 7
3
2 100
2 1 2

10