A729.小伟的购物计划

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

小伟家购置了新房子,有了他自己的房间,他需要购买一些物品。妈妈对他说:“你的房间需要购买什么物品,怎么布置,你说了算,但不超过 NN 元钱”。小伟开始做预算,可他想买的东西太多了,若全买肯定会超过妈妈限定的预算 NN 元。于是他把每件物品规定了一个重要度,分为 55 等:用整数 151−5 表示,第 55 等最重要。
他还查到了每件物品的价格(都是整数)。他希望在不超过 NN 元(可以等于 NN 元)的前提下,使每件物品的价格与重要度的乘积的总和最大。
设第 jj 件物品的价格为 v[j]v[j],重要度为 w[j]w[j],共选中了 kk 件物品,编号依次为 j<sub>1</sub>,j<sub>2</sub>,…,j<sub>k</sub>,则所求的总和为:

v[j<sub>1</sub>]×w[j<sub>1</sub>]+v[j<sub>2</sub>]×w[j<sub>2</sub>]+.......+v[j<sub>k</sub>]×w[j<sub>k</sub>]

请你帮助小伟设计一个满足要求的购物单。

输入格式

第一行,为 22 个正整数,用一个空格隔开:nn mm(其中n<30000n<30000)表示总钱数,m<25m<25为希望购买物品的个数。)
从第22行到第 m+1m+1 行,第 jj 行给出了编号为 j1j−1 的物品的基本数据,每行有 22 个非负整数 vv pp (其中 vv 表示该物品的价格(v10000v≤10000),pp 表示该物品的重要度(151−5)

输出格式

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

输入输出样例

  • 输入#1

    1000 5
    800 2
    400 5
    300 5
    400 3
    200 2

    输出#1

    3900
首页