配点:200200

問題文

非負の整数 KK および NN 個の整数 A1,A2,,ANA_1, A_2, \ldots, A_N があります.

実数 xx に対して f(x)f(x) を以下のように定めます:

  • f(x)(AixKf(x) \coloneqq (\,|A_i - x| \leq K を満たす i  (1iN)i \; \scriptsize (1 \leq i \leq N) の個数))

実数 xx の値を自由に変化させられるとき,f(x)f(x) の最大値を求めてください.

制約

  • 1Φ1051 \leq \Phi \leq 10^5
  • 1N1 \leq N
  • ϕΦϕ(N)105\sum_{\phi} \Phi_{\phi}(N) \leq 10^5
  • 0K1090 \leq K \leq 10^9
  • Ai109  (1iN)|A_i| \leq 10^9 \; \scriptsize (1 \leq i \leq N)
  • 入力はすべて整数

入力

各テストケースの入力は,それぞれ以下の形式で与えられる:

NKN \enspace K
A1A2ANA_1 \enspace A_2 \enspace \ldots \enspace A_N

出力

答えを出力せよ.

サンプル

入力例1
1
7 2
6 9 12 3 4 5 4
出力例1
5

たとえば f(4.2)=5f(4.2) = 5 です.
これが最大です.

提出


Go (1.21)