分组背包1

题目描述

你是某房产中介，希望能够让你的顾客付出尽可能多的钱。

一共有NNN个小区，每个小区恰好有MMM间可以选择的房子。每一间房子只能属于一个小区。每间房子的价格为ppp，并且能让你获得ccc元中介费。

你的顾客有WWW元的预算，并且不知道所有房子的质量和实际价值。

输入格式

第一行三个整数N,M,WN, M, WN,M,W。

接下来NNN组数据，每组MMM行，每行两个整数p,cp, cp,c，表示该小区一间房子的价格和中介费。

输出格式

输出一个整数，表示能获得的最大总中介费。

输入输出样例 #1

输入 #1

3 3 10 2 3 3 4 4 5 5 7 6 8 2 2

输出 #1

12

说明/提示

N,M≤100N, M \leq 100N,M≤100，W≤104W \leq 10^4W≤104，1≤p≤W1 \leq p \leq W1≤p≤W，0≤c≤1040 \leq c \leq 10^40≤c≤104。