背景

GESP四级真题(202406)

描述

⼩杨发现了 $n$ 个宝箱，其中第 $i$ 个宝箱的价值是 $a_i$。

⼩杨可以选择⼀些宝箱放⼊背包并带⾛，但是⼩杨的背包⽐较特殊，假设⼩杨选择的宝箱中最⼤价值为 $x$ ，最⼩价值为 $y$ ，⼩杨需要保证 $x-y \le k$ ，否则⼩杨的背包会损坏。

⼩杨想知道背包不损坏的情况下，⾃⼰能够带⾛宝箱的总价值最⼤是多少。

格式

输入

第⼀⾏包含两个正整数 $n, k$ ，含义如题⾯所⽰。

第⼆⾏包含 $n$ 个正整数 $a_1, a_2, ..., a_n$ ，代表宝箱的价值。

输出

输出⼀个整数，代表带⾛宝箱的最⼤总价值。

样例

5 1 
1 2 3 1 2

7

样例解释

在背包不损坏的情况下，⼩杨可以拿⾛两个价值为 2 的宝箱和⼀个价值为 3 的宝箱。

数据规模

对于全部数据，保证有$ 1 \le n \le 1000, 0 \le k \le 1000, 1 \le a_i \le 1000 $。

限制

时间限制：1.0 s

空间限制：512.0 MB