题目描述

小D将要参加露营啦, 可是他并没有合适大的背包, 这个背包最多装载体积为 $V$ 的东西 ，他想起来家里有 $n$ 块布料, 这 $n$ 块布料可以经过小D的加工后可以使背包扩大的容积, 第 $i$ 块可以扩大 $p_i$ 的容积, 但小D也是人, 他在扩充背包的同时, 对于第 $i$ 块布料, 需要消耗 $q_i$ 的精力.

扩展完背包后, 接下来是装露营所需要的东西了. 一共有 $m$ 个露营用品, 对于第 $i$ 个用品, 它的体积为 $v_i$, 重要度为 $w_i$. 当然, 每个用品都有它独特的重量, 所以小D在把他们放进背包中同样需要 $q_i$ 的精力. 小D也是人! 他有一个精力值上限, 为$L$, 如果他太累了, 就不能去露营了.

现在小D求助你, 他想知道他在精力不被耗光, 背包不会溢出的情况下最大重要度是多少?

输入格式

第一行四个整数, 分别为 $n\ m\ L\ V$

第二到第 $n+1$ 行, 每行有两个整数, 分别为 $p_i$ 和 $q_i$

接下来 $m$ 行, 每行有三个整数, 分别为 $v_i\ w_i\ q_i$

输出格式

一个整数, 表示小D在精力不被耗光, 背包不会溢出的情况下的最大重要度.

样例输入

3 5 7 10
10 2
5 1
1 1
10 10 5
1 1 1
23 2 4
9 5 2
1 20 1

样例输出 #2

36

提示

$1≤n,m,L≤100$

$1\le V \le 10$

$1\le p_i, q_i, v_i, w_i\le 100$

#include<bits/stdc++.h>
using namespace std;

const int N = 105, M = 105;

int n, m, l, V;
int p[N], q[N], v[N], w[N], s[N];
int f[M][10020], g[M];

int main(){
    cin >> n >> m >> V >> l;
    
    for (int i = 1; i <= n; ++ i ) cin >> p[i] >> q[i];
    for (int i = 1; i <= m; ++ i ) cin >> v[i] >> w[i] >> s[i];
    
    int ans = 0;
    for (int Q = 0; Q <= l; ++ Q ) {
    	memset(f, 0, sizeof f);
    	memset(g, 0, sizeof g);
    	
		for (int i = 1; i <= n; ++ i )
			for (int j = Q; j >= q[i]; -- j)
				g[j] = max(g[j], g[j - q[i]] + p[i]);
		cout << g[Q] << " "; 	
		
		for (int i = 1; i <= n; ++ i )	
			for (int j = V + g[Q]; j >= v[i]; -- j)
				for (int k = l - Q; k >= s[i]; -- k)  
					f[j][k] = max(f[j][k], f[j - v[i]][k - s[i]] + w[i]);
		ans = max(ans, f[V + g[Q]][l - Q]);
	}
    
    cout << ans;
    
    return 0;
}