文件读写

• 输入文件picnic.in
• 输出文件picnic.out

限制

• 1000ms
• 512MB

题目描述

程老师要带学生去野餐。采购部准备了 $n$ 种食物，每种食物只有一份，第 $i$ 份食物的重量为 $w_i$，美味值为 $v_i$。

程老师有一个最大承重为 $W$ 的野餐篮。此外，篮子的格子数量有限，最多只能放 $k$ 份食物（放不下的就得留在学校了）。

程老师想知道，在不超过篮子承重、且不超过篮子格子数的前提下，能带走的最大美味值总和是多少。

输入格式

输入第一行包含三个正整数 $n, W, k$，分别表示食物种类数、篮子最大承重和最多能放的食物份数。

接下来 $n$ 行，每行包含两个正整数 $w_i, v_i$，表示第 $i$ 份食物的重量和美味值。

输出格式

输出一行一个整数，表示能带走的最大美味值总和。如果一份都不带，答案为 $0$（但数据保证至少能带走一份）。

数据范围

特殊性质 A：$k = 1$。

特殊性质 B：所有食物的重量 $w_i$ 都相同。

对于 $100\%$ 的数据，保证 $1 \leq n \leq 200$，$1 \leq W \leq 5000$，$1 \leq k \leq \min(n, 20)$，$1 \leq w_i \leq 10^3$，$1 \leq v_i \leq 10^6$。

3 10 2
4 6
5 8
3 4

14

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

14

样例解释

样例2：选第 2、3、5 份食物的总重量为 $5 + 3 + 2 = 10 \leq W$，总美味值为 $8 + 4 + 3 = 15$，但共 $3$ 份，超过 $k = 2$ 的份数限制。在不超过 $2$ 份的前提下，最优方案为选第 1、2 份（总重量 $9$，总美味值 $14$）或选第 3、4 份（总重量 $10$，总美味值 $14$）。