B - Bulk Purchase Discount Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 333 点

問題文

高橋君はスーパーマーケットで N 個の商品を買おうとしています。j 番目の商品の定価は C_j 円です。高橋君は N 個の商品をすべて購入しなければなりません。

このスーパーでは、1回の会計での合計金額に応じてティア制の割引サービスを実施しています。ティアは 1 から K までの 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 に適用されるティアは、T_i \leq X を満たす最大の i です。そのティアの割引率 P_i ％が適用され、割引額は \lfloor X \times P_i / 100 \rfloor 円（小数点以下切り捨て）となります。したがって、スーパーでの支払金額は X - \lfloor X \times P_i / 100 \rfloor 円です。

高橋君はこのスーパーでの会計を1回だけ行います。レジに持っていく前に、カートから任意の商品を棚に戻すことができます。棚に戻した商品は別の店で定価のまま（割引なしで）購入します。

具体的には、高橋君は N 個の商品から部分集合 A（空集合でもよい）を選んでスーパーのレジに持っていきます。A に含まれる商品の定価の合計を X とすると、高橋君が支払う総額は以下の合計です：

  • スーパーでの支払金額：X - \lfloor X \times P_i / 100 \rfloor 円（X に対応するティア i の割引率 P_i を適用）
  • 別の店での支払金額：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
  • 1 行目には、商品の個数 N とティアの段階数 K がスペース区切りで与えられる。
  • 2 行目には、各ティアの適用下限金額 T_i と割引率 P_i の組が K 個、T_1, P_1, T_2, P_2, \ldots, T_K, P_K の順にスペース区切りで与えられる。
  • 3 行目には、N 個の整数 C_1, C_2, \ldots, C_N がスペース区切りで与えられる。

出力

高橋君が支払う総額の最小値を1行で出力してください。

入力例 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

Score : 333 pts

Problem Statement

Takahashi is trying to buy N items at a supermarket. The regular price of the j-th item is C_j yen. Takahashi must purchase all N items.

This supermarket offers a tiered discount service based on the total amount in a single checkout. There are K tiers, numbered from 1 to K. Each tier i has a minimum threshold amount T_i yen and a discount rate P_i%. The tier thresholds satisfy T_1 < T_2 < \cdots < T_K, and in particular T_1 = 0. The discount rates satisfy P_1 \leq P_2 \leq \cdots \leq P_K.

Let X yen be the total amount at checkout. The tier applied to X is the largest i such that T_i \leq X. The discount rate P_i% of that tier is applied, and the discount amount is \lfloor X \times P_i / 100 \rfloor yen (rounded down). Therefore, the payment at the supermarket is X - \lfloor X \times P_i / 100 \rfloor yen.

Takahashi will check out at this supermarket exactly once. Before going to the register, he can return any items from his cart to the shelves. Items returned to the shelves will be purchased at another store at their regular price (without any discount).

Specifically, Takahashi selects a subset A (possibly empty) of the N items to bring to the supermarket register. Let X be the sum of the regular prices of the items in A. The total amount Takahashi pays is the sum of:

  • Payment at the supermarket: X - \lfloor X \times P_i / 100 \rfloor yen (applying the discount rate P_i of the tier i corresponding to X)
  • Payment at the other store: the sum of the regular prices of the items not in A

Find the minimum total amount Takahashi pays when he optimally chooses the subset A.

Constraints

  • 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)
  • All inputs are integers

Input

The input is given in the following format.

N K
T_1 P_1 T_2 P_2 \ldots T_K P_K
C_1 C_2 \ldots C_N
  • The first line contains the number of items N and the number of tiers K, separated by a space.
  • The second line contains K pairs of the minimum threshold amount T_i and the discount rate P_i for each tier, given in the order T_1, P_1, T_2, P_2, \ldots, T_K, P_K, separated by spaces.
  • The third line contains N integers C_1, C_2, \ldots, C_N, separated by spaces.

Output

Print the minimum total amount Takahashi pays, on a single line.

Sample Input 1

3 3
0 0 10 10 20 20
6 8 15

Sample Output 1

24

Sample Input 2

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

Sample Output 2

33

Sample Input 3

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

Sample Output 3

385

Sample Input 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

Sample Output 4

4836500000

Sample Input 5

1 1
0 100
1000000000

Sample Output 5

0