买东西

题目描述

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

一开始背包里已经有 m 件不同的物品（这些物品不能卖、也不能移动出包），等价于先占用了 m 个格子。

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

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

lcy0x1 想在一次购物中，把新买的物品尽量装进行李（不超过剩余格子数），使总花费最大。求这次最多能花多少钱。

说明：购买时只考虑装包容量限制——每个格子只能放同一种物品，且至多 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 出现多行），视为同一种物品，允许在同一格内叠放，只要未超过该种物品在该格的容量上限。