题目背景

Day 2 Problem A.

题面译自 EGOI2021 shoppingfever。

题目描述

海蒂在一个大商店中。她希望购买 $n$ 个商品。

今天是她的幸运日。商店正在进行促销活动：对于每笔账单，顾客获得以下两种优惠之一：

1. 如果买了至少 $3$ 件商品，最便宜的一个免费。
2. 如果买了少于 $3$ 件商品，这笔账单获得 $q\%$ 的折扣。

海蒂希望不重复地买所有 $n$ 件商品。她可以分成任意笔账单购买。对于每笔账单，将会按照对应的优惠政策打折。

她买所有 $n$ 件商品至少需要多少钱？

输入格式

第一行两个整数 $n,q$——商品数和买少于 $3$ 件时的折扣比例。

第二行 $n$ 个整数 $p_i$——商品的价格。

另外，保证商品价格可以被 $100$ 整除。因此，每笔账单折扣的价格永远为整数。

输出格式

一行，一个整数——至少需要的钱数。

7 10
300 200 200 300 100 300 200

1090

3 20
1000 500 100

1280

4 0
200 100 300 200

600

提示

样例 $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$ 分）：无特殊限制。