分数: 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