题目描述

题目译自 European Girls' Olympiad in Informatics 2021 Day2 T1. Shopping Fever

海蒂来到一家大商场，她想要购买 $n$ 件商品。今天是她的幸运日，商场正在举行特别促销活动：每次购买时，顾客可以享受以下两种优惠之一：

1. 如果一次购买至少 $3$ 件商品，最便宜的那件免费。
2. 如果一次购买少于 $3$ 件商品，顾客可以享受 $q\%$ 的折扣。

海蒂希望买齐购物清单上的所有 $n$ 件商品，每件恰好买一次。她可以进行任意次数的购买，每次购买都会自动应用相应的优惠。

你的任务是帮她计算购买所有 $n$ 件商品所需的最小总费用。

输入格式

第一行包含两个用空格分隔的整数 $n,q$ $(1 \leq n \leq 100000, 0 \leq q \leq 100)$，分别表示海蒂想购买的商品数量和购买少于三件商品时的折扣百分比。

第二行包含 $n$ 个用空格分隔的整数 $p_1, \ldots, p_n$ $(100 \leq p_i \leq 100000, 1 \leq i \leq n)$，表示每件商品的价格。

此外，保证每个 $p_i$ 都能被 $100$ 整除。因此，每次购买的折扣价格始终为整数。

输出格式

输出一个整数，表示海蒂购买所有 $n$ 件商品所需的最小总费用。

7 10
300 200 200 300 100 300 200

1090

海蒂可以先一次性购买三件价格为 $200$ 的商品，花费 $400$（其中一件免费）。然后，她再购买三件价格为 $300$ 的商品，花费 $600$（同样一件免费）。最后，她单独购买剩余的一件价格为 $100$ 的商品，享受 $10\%$ 的折扣，花费 $90$。总费用为 $400 + 600 + 90 = 1090$。

3 20
1000 500 100

1280

如果海蒂一次性购买所有三件商品（价格为 $1000, 500, 100$），她将获得 $100$ 的折扣，总费用为 $1500 - 100 = 1400$。但如果她分别单独购买每件商品，折扣为 $(1000 + 500 + 100) \cdot 20 / 100 = 320$，总费用为 $1600 - 320 = 1280$，这更便宜。

4 0
200 100 300 200

600

数据范围与提示

详细子任务附加限制及分值如下表所示。