买东西 2

题目描述

lcy0x1 背着背包去商店买东西。背包共有 21 个格子。

起初背包里已有 m 件不同的物品（不能出售，也不能移出背包），等价于先占用了 m 个格子。

商店里有 n 种可购买的物品。对第 i 种物品，给出：

• 名称 st_i；
• 库存数量 a_i（最多可买的件数）；
• 单价 b_i（每件需支付的金额）；
• 每格容量 c_i（同一格内只能放同一种物品，且最多放 c_i 件；同名物品可叠放，未满可继续叠）。

现在希望在一次购物中，把新买的物品装入背包（不超过剩余格子数），使总花费最大。请计算本次最多能花多少钱。

说明：只考虑装包限制。每格只能放一种物品，且该格内最多放 c_i 件；购买的总件数不得超过对应库存 a_i；已占用的 m 个格子不能使用。输出的是新购商品的最大总花费（支付金额之和）。

输入格式

• 第一行两个整数 m, n。
• 接下来的 n 行，每行包含三个整数 a_i, b_i, c_i 和一个字符串 st_i，表示一种物品。

输出格式

• 输出一个整数 s，表示一次购物最多能花费的金额。

样例

输入

20 3
63 1 64 yinshifen
1 10 1 men
1 1 64 yinshifen

输出

64

说明/提示

• 数据范围：

  • 0 ≤ m ≤ 21
  • 0 ≤ n ≤ 100
  • 0 ≤ a_i ≤ 1344
  • 0 ≤ b_i ≤ 10^4
  • 0 < c_i ≤ 64
  • 0 < |st_i| < 100
  • 0 ≤ s ≤ 10^6
• 同种判定：若输入中同名物品（相同 st_i）出现多行，则仅当其 b 与 c 也相同，才视为同一种物品；同一种物品可以在同一格内叠放，且不能超过该格对该物品的容量上限 c。