[EGOI 2021] Shopping Fever / 购物热

海蒂在一个大商店中。她希望购买 $n$ 个商品。 今天是她的幸运日。商店正在进行促销活动：对于每笔账单，顾客获得以下两种优惠之一： 1. 如果买了至少 $3$ 件商品，最便宜的一个免费。 2. 如果买了少于 $3$ 件商品，这笔账单获得 $q\%$ 的折扣。 海蒂希望不重复地买所有 $n$ 件商品。她可以分成任意笔账单购买。对于每笔账单，将会按照对应的优惠政策打折。 她买所有 $n$ 件商品至少需要多少钱？ ## Input 第一行两个整数 $n,q$——商品数和买少于 $3$ 件时的折扣比例。 第二行 $n$ 个整数 $p_i$——商品的价格。 另外，保证商品价格可以被 $100$ 整除。因此，每笔账单折扣的价格永远为整数。 ## Output 一行，一个整数——至少需要的钱数。 [samples] ## Background Day 2 Problem A. 题面译自 [EGOI2021 shoppingfever](https://stats.egoi.org/media/task_description/2021_shoppingfever_en.pdf)。 ## Note **样例 $1$ 解释** 海蒂先购买三个价格为 $200$ 元的商品，花费 $400$ 元（免费获得了一个商品）。再购买三个价格为 $300$ 元的商品，花费 $600$ 元（同样免费获得一个）。最后，她购买剩余的价格为 $100$ 元的商品，获得 $10\%$ 的折扣。 --- **样例 $2$ 解释** 如果海蒂用一笔账单购买三个商品，她获得 $100$ 元的折扣。然而，如果她分三次购买三个商品，获得的折扣变为 $(1000+500+100)\cdot\frac{20}{100}=320$ 元。 --- **数据范围** 对于全部数据，$1\le n\le 10^5$，$0\le q\le 100$，$100\le p_i\le 10^5$ 且 $100\mid p_i$。 - 子任务一（$8$ 分）：$n=3$，$100\le p_i\le 10^3$。 - 子任务二（$18$ 分）：$q=0$。 - 子任务三（$16$ 分）：$q=40$。 - 子任务四（$22$ 分）：$100\le p_i\le 10^3$。 - 子任务五（$36$ 分）：无特殊限制。