Suma màxima P34239


Statement
 

pdf   zip

thehtml

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 | x − y | ≥ 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 ≤ n ≤ 104, 1 ≤ d ≤ 105, i que els elements donats estan entre 1 i 105.

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

    100000
70
40
10
6
149
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++