← 返回题目列表

AtCoder · awc0079_b

B. 批量购买折扣

中文机器翻译题面 查看原题

分数: 333 分

问题陈述

高桥正在尝试购买 N 超市里的物品。正常价格为 j- 第一项是 C_j 日元。高桥必须全部购买 N 项目。

该超市根据单次结账总额提供分级折扣服务。有 K 层,编号自 1 to K。每层 i 有最低阈值金额 T_i 日元和折扣率 P_i%。等级阈值满足 T_1 < T_2 < \cdots < T_K,特别是 T_1 = 0。折扣率满足 P_1 \leq P_2 \leq \cdots \leq P_K.

让 X 日元为结账时的总金额。等级适用于 X 是最大的 i 这样 T_i \leq X。折扣率 P_i应用该等级的 %,折扣金额为 \lfloor X \times P_i / 100 \rfloor 日元(向下舍入)。因此,超市付款方式为 X - \lfloor X \times P_i / 100 \rfloor 日元。

高桥只会在这家超市结账一次。在去收银台之前,他可以将购物车中的任何物品放回到货架上。退回货架的商品将在另一家商店按正常价格购买(无任何折扣)。

具体来说,高桥选择了一个子集 A (可能为空) N 带到超市收银台的物品。让 X 是商品正常价格的总和 A。高桥支付的总金额为:

  • 超市付款: X - \lfloor X \times P_i / 100 \rfloor 日元(应用折扣率 P_i 等级 i 对应于 X)
  • 在其他商店付款:不在该商店的商品正常价格的总和 A

求高桥最优选择子集时支付的最小总金额 A.

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 2 \times 10^5
  • 0 = T_1 < T_2 < \cdots < T_K \leq 2 \times 10^{14}
  • 0 \leq P_1 \leq P_2 \leq \cdots \leq P_K \leq 100
  • 1 \leq C_j \leq 10^9 (1 \leq j \leq N)
  • 所有输入均为整数

输入

输入按以下格式给出。

N K
T_1 P_1 T_2 P_2 \ldots T_K P_K
C_1 C_2 \ldots C_N
  • 第一行包含项目数 N 和层数 K,用空格分隔。
  • 第二行包含 K 对最低金额阈值 T_i 和折扣率 P_i 对于每个层,按顺序给出 T_1, P_1, T_2, P_2, \ldots, T_K, P_K,以空格分隔。
  • 第三行包含 N 整数 C_1, C_2, \ldots, C_N,以空格分隔。

输出

在一行上打印 Takahashi 支付的最低总金额。


示例输入 1

3 3
0 0 10 10 20 20
6 8 15

示例输出 1

24

示例输入 2

4 4
0 0 30 10 60 10 61 50
10 20 31 5

示例输出 2

33

示例输入 3

7 5
0 0 50 5 120 12 200 20 350 25
17 33 45 60 88 120 150

示例输出 3

385

示例输入 4

12 8
0 0 500000000 2 1000000000 3 2000000000 5 3000000000 7 4000000000 10 5500000000 15 200000000000000 17
999999999 850000000 760000000 640000000 530000000 470000000 390000000 310000000 280000000 220000000 150000000 90000000

示例输出 4

4836500000

示例输入 5

1 1
0 100
1000000000

示例输出 5

0