問題文

JOI くんと IOI ちゃんは兄妹であり，今日は IOI ちゃんの誕生日である．JOI くんは IOI ちゃんの誕生日を祝うために N 個のケーキを購入した．ケーキには 1 から N までの番号が付けられており，ケーキ i (1 \leqq i \leqq N) の大きさは A_i である． JOI くんは IOI ちゃんを喜ばせようと考え，N 個の計画を立てた．i 番目 (1 \leqq i \leqq N) の計画は，ケーキ i に甘さ V_i のいちごを 1 個飾りつけることである．

JOI くんはケーキの見栄えにもこだわりがあるため，以下の条件をすべて満たすように 0 個以上のいくつかの計画を選んで実行する．

• いちごが飾りつけられた相異なる 2 つのケーキについて，それらのケーキの大きさの和は S ではない．
• いちごが飾りつけられた相異なる 2 つのケーキについて，それらのケーキの大きさの差は D ではない．

実行する計画の個数が 1 つ以下のとき，条件は必ず満たされることに注意せよ．

IOI ちゃんは甘いものが好物であるため，飾りつけられたいちごの甘さの合計をなるべく大きくしたい．ここで，1 つもいちごを飾りつけなかった場合，飾りつけられたいちごの甘さの合計は 0 とする．

ケーキといちごの情報が与えられたとき，飾りつけられたいちごの甘さの合計としてありうる最大値を求めるプログラムを作成せよ．

制約

• 1 \leqq N \leqq 200\,000．
• 1 \leqq S \leqq 10^9．
• 1 \leqq D \leqq 10^9．
• 1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N)．
• 1 \leqq V_i \leqq 10^9 (1 \leqq i \leqq N)．
• 入力される値はすべて整数である．

小課題

1. (7 点) N \leqq 20．
2. (14 点) S \leqq 40，D \leqq 20，A_i \leqq 20 (1 \leqq i \leqq N)．
3. (18 点) S = 1．
4. (30 点) D = 1，S は奇数．
5. (15 点) D = 1．
6. (16 点) 追加の制約はない．

入力例 1

5 8 3
3 4 5 6 7
10 6 7 5 4

出力例 1

18

計画 2,3,4 を選び，実行することを考える． いちごが飾りつけられたケーキ 2,3,4 の中からどのように相異なる 2 つを選んでも，大きさの和が 8 となることや差が 3 となることはない． したがって，これらの計画は実行可能である． ここで，飾りつけられたいちごの甘さの合計は 6 + 7 + 5 = 18 となる．

甘さの合計が 18 より大きくなるような計画の選び方は存在しないため，18 を出力する．

この入力例は小課題 1,2,6 の制約を満たす．

入力例 2

3 1 3
4 7 10
3 10 8

出力例 2

11

この入力例は小課題 1,2,3,6 の制約を満たす．

入力例 3

10 1 1
1 2 3 4 5 6 7 8 9 10
3 1 4 1 5 9 2 6 5 3

出力例 3

25

この入力例はすべての小課題の制約を満たす．