A370 | $小伟的购物计划$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

小伟家购置了新房子，有了他自己的房间，他需要购买一些物品。妈妈对他说：“你的房间需要购买什么物品，怎么布置，你说了算，但不超过 $N$ 元钱”。小伟开始做预算，可他想买的东西太多了，若全买肯定会超过妈妈限定的预算 $N$ 元。于是他把每件物品规定了一个重要度，分为 $5$ 等：用整数 $1−5$ 表示，第 $5$ 等最重要。 他还查到了每件物品的价格（都是整数）。他希望在不超过 $N$ 元（可以等于 $N$ 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。 设第 $j$ 件物品的价格为 $v[j]$，重要度为 $w[j]$，共选中了 $k$ 件物品，编号依次为 $j_{1},j_{2},…,j_{k}$，则所求的总和为： $v[j_{1}]\times w[j_{1}]+v[j_{2}]\times w[j_{2}]+.......+v[j_{k}]×w[j_{k}]$ 请你帮助小伟设计一个满足要求的购物单。

第一行，为 $2$ 个正整数，用一个空格隔开：$n$ $m$（其中$n<30000$)表示总钱数，$m<25$为希望购买物品的个数。) 从第$2$行到第 $m+1$ 行，第 $j$ 行给出了编号为 $j-1$ 的物品的基本数据，每行有 $2$ 个非负整数 $v$ $p$ (其中 $v$ 表示该物品的价格($v\leq10000$)，$p$ 表示该物品的重要度($1-5$)

$1$ 个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值($<100000000$)。

输入 #1

输出 #1

C++ 编辑器

输入

输出