该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

变速烤箱

题目描述

厨房中有两台烤箱。第一台烤箱的加热速度较慢：如果一道菜的标准烹饪时间为 $T_i$ 分钟，那么它在第一台烤箱中需要 $A\times T_i$ 分钟；同一道菜在第二台烤箱中需要 $T_i$ 分钟。

共有 $N$ 道菜，每道菜必须完整地放入其中一台烤箱烹饪，不能在烹饪过程中更换烤箱。每台烤箱同一时刻至多烹饪一道菜，两台烤箱可以同时工作，且都从时刻 $0$ 开始。每台烤箱内各道菜的烹饪顺序可以任意安排。

请合理分配所有菜，使最后一道菜完成的时刻尽可能早，并输出这个最早时刻。

输入格式

输入共两行。

第一行包含两个整数 $N,A$。

第二行包含 $N$ 个整数 $T_1,T_2,\ldots,T_N$。

• $2\le N\le 100$
• $2\le A\le 5$
• $1\le T_i\le 1000$
• 输入中的所有数均为整数

输出格式

输出一个整数，表示最后一道菜完成的最早时刻。

输入输出样例 #1

输入 #1

3 2
2 3 5

输出 #1

7

输入输出样例 #2

输入 #2

2 2
1 1

输出 #2

2

说明/提示

对于样例 1，可以把标准烹饪时间为 $3$ 的菜分给第一台烤箱，它需要 $2\times 3=6$ 分钟；把另外两道菜分给第二台烤箱，它们共需要 $2+5=7$ 分钟。两台烤箱同时工作，因此所有菜在时刻 $7$ 完成。不存在更快的分配。

对于样例 2，如果两道菜分别放入两台烤箱，第一台烤箱在时刻 $2$ 完成，第二台烤箱在时刻 $1$ 完成，所以答案为 $2$。