08765. 联欢会布置预算 · 林老师的题库

题目描述

元旦联欢会前，班主任拨给班级 $n$ 元班费作为教室布置预算。文艺委员列出了 $m$ 件候选装饰材料（彩灯、横幅、气球门、小舞台灯等），第 $j$ 件材料单价 $v_{j}$ 元，布置效果的重要度为 $w_{j}$ ，用 $1 \sim 5$ 的整数表示， $5$ 表示最重要。每件材料最多购买一件。

同学们约定用花费与重要度的乘积来衡量买下材料的满足程度：若最终购买了编号为 $j_{1}, j_{2}, \dots, j_{k}$ 的材料，则满足度为

v_{j_{1}} \times w_{j_{1}} + v_{j_{2}} \times w_{j_{2}} + \dots + v_{j_{k}} \times w_{j_{k}}

在总花费不超过 $n$ 元的前提下，满足度最大是多少？

输入格式

第一行两个整数 $n$ 和 $m$ ，表示布置预算（元）与候选材料件数。

接下来 $m$ 行，第 $j$ 行两个整数 $v_{j}$ 和 $w_{j}$ ，表示第 $j$ 件材料的单价与重要度。

输出格式

一行一个整数，表示总花费不超过 $n$ 元时满足度的最大值。

样例

输入

输出

样例解释：购买第 $1$ 、 $2$ 件材料，花费 $500 + 300 = 800$ 元，不超过预算 $900$ 元，满足度 $500 \times 3 + 300 \times 5 = 3000$ ；其余方案的满足度都不超过 $3000$ 。

样例解释：两件材料的单价都超过预算 $200$ 元，一件也买不起，满足度为 $0$ 。

数据范围

对于 $100%$ 的数据： $0 \leq n \leq 1 0^{4}$ ， $1 \leq m \leq 100$ ， $1 \leq v_{j} \leq 1600$ ， $1 \leq w_{j} \leq 5$ 。

本题共 $10$ 个测试点，每个测试点 $10$ 分。

08765. 联欢会布置预算 未做

题目描述

输入格式

输出格式

样例

数据范围

08765. 联欢会布置预算未做