#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;

const int MAX_N = 500 + 9;

int n, m, a[MAX_N], dp[MAX_N][MAX_N];

int dfs(int i, int st) {
	if (i == n + 1) return 0;
	if (st < a[i]) return dfs(i, a[i]);
	if (dp[i][st - a[i]]) return dp[i][st - a[i]];
	
	int sum = 0, j = i;
	while (j <= n && a[j] <= st) sum += a[j++];
	int res = st * (j - i) - sum + dfs(j, st + m);
	for ( ; j <= n; j++) {
		sum += a[j];
		res = min(a[j] * (j - i + 1) - sum + dfs(j + 1, a[j] + m), res);
	}
	return dp[i][st - a[i]] = res;
}

void solve() {
	sort(a + 1, a + n + 1);
	printf("%d\n", dfs(1, 0));
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	solve();
	return 0; 
}
测试点 #1
Accepted
得分:100
用时:2 ms
内存:228 KiB

输入文件(bus1.in

10 1
94 18 18 85 64 27 70 81 83 0
输出文件(bus1.ans
0
选手输出
0

测试点 #2
Accepted
得分:100
用时:2 ms
内存:228 KiB

输入文件(bus2.in

10 1
30 54 99 19 29 55 97 7 89 72
输出文件(bus2.ans
0
选手输出
0

测试点 #3
Accepted
得分:100
用时:2 ms
内存:228 KiB

输入文件(bus3.in

20 2
0 0 0 91 94 93 0 94 92 97 0 0 0 97 0 0 95 94 0 96
输出文件(bus3.ans
5
选手输出
5

测试点 #4
Accepted
得分:100
用时:2 ms
内存:228 KiB

输入文件(bus4.in

20 2
85 85 84 96 0 0 85 82 97 83 82 95 85 94 0 0 82 0 83 0
输出文件(bus4.ans
6
选手输出
6

测试点 #5
Accepted
得分:100
用时:2 ms
内存:228 KiB

输入文件(bus5.in

20 2
82 84 82 0 82 84 82 82 0 81 83 84 83 94 0 95 84 0 85 83
输出文件(bus5.ans
6
选手输出
6

测试点 #6
Accepted
得分:100
用时:2 ms
内存:228 KiB

输入文件(bus6.in

20 2
94 0 75 78 84 79 77 83 83 95 74 76 83 76 75 74 0 85 79 84
输出文件(bus6.ans
8
选手输出
8

测试点 #7
Accepted
得分:100
用时:12 ms
内存:1260 KiB

输入文件(bus7.in

500 100
1285 2901 8928 8162 3321 2842 2122 326 6364 3184 9285 3328 2771 6151 9977 3794 1118 5627 8561 3543 8235 6472 1906 3030 2
<2310 bytes omitted>
输出文件(bus7.ans
18401
选手输出
18401

测试点 #8
Accepted
得分:100
用时:11 ms
内存:1296 KiB

输入文件(bus8.in

500 100
3512 2145 3757 9889 5195 3886 2116 6257 2812 4523 6217 4559 2275 6562 2627 5425 1181 949 38 9588 9366 5440 6158 1614 441
<2330 bytes omitted>
输出文件(bus8.ans
18644
选手输出
18644

测试点 #9
Accepted
得分:100
用时:12 ms
内存:1264 KiB

输入文件(bus9.in

500 100
1191 3663 3560 8731 8330 7058 5971 9489 9197 4204 658 204 1461 6031 4192 5087 2841 3942 8507 5002 1706 9762 2005 6736 33
<2330 bytes omitted>
输出文件(bus9.ans
18078
选手输出
18078

测试点 #10
Accepted
得分:100
用时:13 ms
内存:1200 KiB

输入文件(bus10.in

500 100
9802 490 7085 3165 6654 7366 9026 9951 587 3619 5109 7635 5405 1615 3346 8535 8470 2404 8277 166 6218 2869 8895 3547 670
<2331 bytes omitted>
输出文件(bus10.ans
18082
选手输出
18082

测试点 #11
Accepted
得分:100
用时:5 ms
内存:1252 KiB

输入文件(bus11.in

500 10
3200069 1200114 3200099 400213 3200009 1200166 3200173 2400096 3200005 3600019 3200000 2800160 2400049 25 1600000 400181 
<3549 bytes omitted>
输出文件(bus11.ans
1370
选手输出
1370

测试点 #12
Accepted
得分:100
用时:5 ms
内存:1236 KiB

输入文件(bus12.in

500 10
800152 140 151 1600128 1600091 1200092 800103 2800009 1600094 3200224 2400044 800091 3200207 1200184 800003 44 800007 800
<3544 bytes omitted>
输出文件(bus12.ans
1361
选手输出
1361

测试点 #13
Accepted
得分:100
用时:5 ms
内存:1252 KiB

输入文件(bus13.in

500 10
2800022 3200176 3600142 1200152 3200110 209 800185 2000056 400162 800086 2400019 2400027 400129 2000141 78 3600182 800225
<3553 bytes omitted>
输出文件(bus13.ans
1386
选手输出
1386

测试点 #14
Accepted
得分:100
用时:6 ms
内存:1292 KiB

输入文件(bus14.in

500 10
3600034 1200035 249 3200162 1600104 2000025 400164 3200081 2800124 1200101 1200146 1600054 2800011 100 800172 800167 1200
<3560 bytes omitted>
输出文件(bus14.ans
1407
选手输出
1407

测试点 #15
Accepted
得分:100
用时:10 ms
内存:1276 KiB

输入文件(bus15.in

500 100
3200719 1201254 3201059 402593 3200219 1201816 3202153 2400976 3200155 3600239 3200000 2802050 2400469 315 1600000 40204
<3599 bytes omitted>
输出文件(bus15.ans
13482
选手输出
13482

测试点 #16
Accepted
得分:100
用时:10 ms
内存:1252 KiB

输入文件(bus16.in

500 100
802102 1670 1881 1601428 1601061 1201132 801473 2800029 1601124 3201834 2400594 801251 3201707 1202064 800053 614 800107
<3605 bytes omitted>
输出文件(bus16.ans
13344
选手输出
13344

测试点 #17
Accepted
得分:100
用时:10 ms
内存:1304 KiB

输入文件(bus17.in

500 100
2800292 3201686 3602052 1201682 3201080 2429 801825 2000886 401532 800816 2400159 2400247 401239 2001661 898 3602382 802
<3606 bytes omitted>
输出文件(bus17.ans
13266
选手输出
13266

测试点 #18
Accepted
得分:100
用时:10 ms
内存:1264 KiB

输入文件(bus18.in

500 100
3600384 1200415 2299 3201572 1601014 2000205 401954 3200901 2801214 1201161 1201556 1600484 2800131 760 802152 802147 12
<3605 bytes omitted>
输出文件(bus18.ans
13366
选手输出
13366

测试点 #19
Accepted
得分:100
用时:11 ms
内存:1280 KiB

输入文件(bus19.in

500 100
2000735 3601218 1201962 2800705 3600092 3201961 2001070 400682 1201408 3601293 2400000 2401585 401814 2400484 401363 120
<3609 bytes omitted>
输出文件(bus19.ans
13357
选手输出
13357

测试点 #20
Accepted
得分:100
用时:11 ms
内存:1228 KiB

输入文件(bus20.in

500 100
1335 2800331 801596 3602124 1601463 2400886 400984 2001403 3202001 3600820 3200538 2069 1201666 2800551 401103 1449 3600
<3603 bytes omitted>
输出文件(bus20.ans
13568
选手输出
13568