当前没有测试数据。

问题描述

已知有$\tt n$个物品，每个物品有其对应的重量$\tt w_i$和对应的价值$\tt p_i$.小明有一个背包，背包由于质量有限，只允许放入$\tt m,m$个物品(必须放满$\tt m$个物品),且物品的重量总和不能超过$\tt W,W\le 1000$,小明想知道背包内放入物品的最大价值。

格式

输入描述

第一行三个整数$\tt n,m,W.$

第二行有$\tt n$个整数,每个数表示物品重量$\tt w_i$

第三行有$\tt n$个整数,每个数表示物品价值$\tt p_i$.

输出描述

一个整数,背包内的最大价值

样例输入

样例输入1

3 2 1000

1 2 3
2 3 4

样例输出1

限制

对于$\tt 100\%$的数据 $\tt 1\le n\le 20,m\le n,W,w_i\le 1000,p_i\le 10^9$

1s, 1024KiB for each test case.