Suma màxima P34239

Statement

Donats $n$ naturals diferents, escolliu-ne un subconjunt de manera que la suma sigui màxima. Només teniu una restricció: per a tot parell $x$ i $y$ d’elements escollits, s’ha de complir $\vert x - y \vert \ge d$ , on $d$ és un natural donat.

Entrada

L’entrada consisteix en diversos casos, només amb enters. Cada cas comença amb $n$ i $d$ , seguits d’ $n$ nombres diferents. Suposeu $1 \le n \le 10^4$ , $1 \le d \le 10^5$ , i que els elements donats estan entre 1 i $10^5$ .

Sortida

Per a cada cas, escriviu la màxima suma possible.

Public test cases

Input

1 100
100000

2 10
30 40

2 11
30 40

4 1
1 2 3 4

4 2
1 2 3 4

7 3
47 27 25 44 48 30 28

Output

Information

Author: Salvador Roura
Language: Catalan
Official solutions: C++
User solutions: C++