Problem: The Shuseki Islands are an archipelago of 30001 small islands in the Yutampo Sea. The islands are evenly spaced along a line, numbered from 0 to 30000 from the west to the east. These islands are known to contain many treasures. There are n gems in the Shuseki Islands in total, and the i-th gem is located on island pi.

Mr. Kitayuta has just arrived at island 0. With his great jumping ability, he will repeatedly perform jumps between islands to the east according to the following process: 

  * First, he will jump from island 0 to island d. 
  * After that, he will continue jumping according to the following rule. Let l be the length of the previous jump, that is, if his previous jump was from island prev to island cur, let l = cur - prev. He will perform a jump of length l - 1, l or l + 1 to the east. That is, he will jump to island (cur + l - 1), (cur + l) or (cur + l + 1) (if they exist). The length of a jump must be positive, that is, he cannot perform a jump of length 0 when l = 1. If there is no valid destination, he will stop jumping. 



Mr. Kitayuta will collect the gems on the islands visited during the process. Find the maximum number of gems that he can collect.

Input

The first line of the input contains two space-separated integers n and d (1 ≤ n, d ≤ 30000), denoting the number of the gems in the Shuseki Islands and the length of the Mr. Kitayuta's first jump, respectively.

The next n lines describe the location of the gems. The i-th of them (1 ≤ i ≤ n) contains a integer pi (d ≤ p1 ≤ p2 ≤ ... ≤ pn ≤ 30000), denoting the number of the island that contains the i-th gem.

Output

Print the maximum number of gems that Mr. Kitayuta can collect.

Examples

Input

4 10
10
21
27
27


Output

3


Input

8 8
9
19
28
36
45
55
66
78


Output

6


Input

13 7
8
8
9
16
17
17
18
21
23
24
24
26
30


Output

4

Note

In the first sample, the optimal route is 0  →  10 (+1 gem)  →  19  →  27 (+2 gems)  → ...

In the second sample, the optimal route is 0  →  8  →  15  →  21 →  28 (+1 gem)  →  36 (+1 gem)  →  45 (+1 gem)  →  55 (+1 gem)  →  66 (+1 gem)  →  78 (+1 gem)  → ...

In the third sample, the optimal route is 0  →  7  →  13  →  18 (+1 gem)  →  24 (+2 gems)  →  30 (+1 gem)  → ...

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class Main {

    static int[][] dp = new int[30001][500];
    static int offset = 250;
    public static void main(String[] args) throws IOException {
        io.init();
//        HW11 hw = new HW11();
        int N = io.i(); int D = io.i();
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = -1;
            }
        }
        int[] freq = new int[30001];
        for (int i = 0; i < N; i++) {
            freq[io.i()]++;
        }
        System.out.println(recur(freq, D, D, D));
        io.close();
        System.exit(0);
    }
    public static int recur(int[] freq, int p, int l, int d) {
        if (p > 30000) return 0;
        if (dp[p][l-d+offset] != -1) return dp[p][l-d+offset];
        int ans = freq[p];
        ans += Math.max(recur(freq, p+l, l, d), recur(freq, p+l+1, l+1, d));
        if (l > 1) ans = Math.max(ans, freq[p] + recur(freq, p+l-1, l-1, d));
        return dp[p][l-d+offset] = ans;
    }

}

/**
 * This is an input reading class designed to speed up input reading.
 * Some of it was adapted from James Brucker's (Dept. of Computer Engineering at Kasetsart University) Lecture Materials
 * Source Link: https://www.cpe.ku.ac.th/~jim/java-io.html
 * This reader class has been shared with some classmates on request.
 */
class io {
    static BufferedReader reader;
    static StringTokenizer tokenizer;
    static BufferedWriter writer;

    /** Constructor method to initialize the reader for input stream */
    static void init() {
        reader = new BufferedReader(new InputStreamReader(System.in));
        writer = new BufferedWriter(new OutputStreamWriter(System.out));
        tokenizer = new StringTokenizer("");
    }

    static void close() throws IOException {
        reader.close();
        writer.flush();
        writer.close();
    }

    static void w(Object o) throws IOException {
        writer.write(o.toString());
    }

    /** This method gets the next word */
    static String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }

    static int i() throws IOException {
        return Integer.parseInt(next());
    }

    static double d() throws IOException {
        return Double.parseDouble(next());
    }

    static Long l() throws IOException {
        return Long.parseLong(next());
    }

    static String s() throws IOException{
        return next();
    }

    static int[] makeArray(int n) throws IOException {
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = io.i();
        }
        return array;
    }

    static int[][] makeArray(int n, int m) throws IOException {
        int[][] array = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                array[i][j] = io.i();
            }
        }
        return array;
    }

    // Read unknown number of lines as integers. Stop at empty line.
    static ArrayList<Integer> readIntegersToArrayList() throws IOException {
        ArrayList<Integer> list = new ArrayList<>();
        String str = null;
        do {
            str = io.reader.readLine();
            if (str == null || str.length() == 0) break;

            list.add(Integer.parseInt(str));

        } while (str != null || str.length() != 0);
        return list;
    }

    // Read unknown number of lines as Strings. Stop at empty line.
    static ArrayList<String> readStringsToArrayList() throws IOException {
        ArrayList<String> list = new ArrayList<>();
        String str = null;
        do {
            str = io.reader.readLine();
            if (str == null || str.length() == 0) break;
            list.add(str);
        } while (str != null || str.length() != 0);
        return list;
    }

    // Read unknown number of lines as Strings. Stop at EOF.
    static ArrayList<String> readStringsToArrayListEOF() throws IOException {
        ArrayList<String> list = new ArrayList<>();
        String str = "";
        while ((str = io.reader.readLine()) != null) {
            if (str.trim().length() == 0) continue;
            list.add(str.trim() + " ");
        }
        return list;
    }

    // Read unknown number of lines as Strings. Stop at specified character "b".
    static ArrayList<String> readStringsToArrayList(String b) throws IOException {
        ArrayList<String> list = new ArrayList<>();
        String str = null;
        do {
            str = io.reader.readLine();
            if (str == null || str.length() == 0 || str.equals(b)) break;
            list.add(str);
        } while (str != null || str.length() != 0);
        return list;
    }

    // Read one line as Strings into an ArrayList.
    static ArrayList<String> splitLineStrings() throws IOException {
        ArrayList<String> list = new ArrayList<>();
        String str = null;
        String[] vals;

        str = io.reader.readLine();
        if (str == null || str.length() == 0) return list;
        vals = str.split(" ");

        for (int i = 0, valsLength = vals.length; i < valsLength; i++) {
            String s = vals[i];
            list.add(s);
        }
        return list;
    }

    // Read one line as Integers into an ArrayList.
    static ArrayList<Integer> splitLineIntegers() throws IOException {
        ArrayList<Integer> list = new ArrayList<>();
        String str = null;
        String[] vals;

        str = io.reader.readLine();
        if (str == null || str.length() == 0) return list;
        vals = str.split(" ");

        for (int i = 0, valsLength = vals.length; i < valsLength; i++) {
            String s = vals[i];
            list.add(Integer.parseInt(s));
        }
        return list;
    }

    // Prints an array with an optional newline
    static void printArray(int[] array, boolean newLine) throws IOException {
        for (int i = 0; i <array.length; i++) {
            io.w(i == array.length - 1 ? array[i] + (newLine ? "\n" : "") : array[i] + " ");
        }
    }
}

class UnionFindR {
    int[] parent, rank = null;
    int count = 0;

    public UnionFindR(int len) {
        this.parent = new int[len];
        this.rank = new int[len];
        this.count = len;
        for (int i = 0; i < len; i++) {
            this.parent[i] = i;
        }
    }

    public int find(int e) {
//        if (parent[e] != e) {
//            parent[e] = find(parent[e]);
//        }
//        return parent[e];
        if (parent[e] == e) return e;
        return e = find(parent[e]);
    }

    public void union(int x, int y) {
        int xRoot = find(x), yRoot = find(y);
        if (xRoot == yRoot) {
            return;
        }
        else if (rank[xRoot] < rank[yRoot]) {
            parent[xRoot] = yRoot;
        }
        else if (rank[yRoot] < rank[xRoot]) {
            parent[yRoot] = xRoot;
        }
        else {
            parent[yRoot] = parent[xRoot];
            rank[xRoot]++;
        }
        count--;
    }

    public int sizeOfSet(int x) {
        int root = find(x);
        int size = 0;
        for (int i = 0; i < parent.length; i++) {
            if (find(parent[i]) == root) {
                size++;
            }
        }
        return size;
    }
}

class UnionFindS {
    int[] size = null;
    int count = 0;

    public UnionFindS(int len) {
        this.size = new int[len];
        this.count = len;
        for (int i = 0; i < len; i++) {
            this.size[i] = -1;
        }
    }

    public int find(int e) {
        if (size[e] < 0) {
            return e;
        }
        return this.size[e] = find(size[e]);
    }

    public void union(int x, int y) {
        int xRoot = find(x), yRoot = find(y);
        if (xRoot == yRoot) return;

        int sizeX = sizeOf(x); int sizeY = sizeOf(y);
        if (sizeX > sizeY) {
            size[xRoot] -= sizeY;
            size[yRoot] = xRoot;
        }
        else {
            size[yRoot] -= sizeX;
            size[xRoot] = yRoot;
        }
        count--;
    }

    public int sizeOf(int e) {
        int index = find(e);
        return -size[index];
    }
}

class Util {

    static int[][] deepCopy(int[][] a) {
        if (a == null) return null;
        int[][] copy = new int[a.length][];
        for (int i = 0; i < a.length; i++) {
            copy[i] = Arrays.copyOf(a[i], a[i].length);
        }
        return copy;
    }

    static List<Integer> generatePrimes(int N) {
        // p(n) < n ln (n ln n) for n >= 6
        final int size = (int) Math.floor(0.5 * (N - 3)) + 1;
        List<Integer> primes = new ArrayList<>();
        List<Boolean> isPrime = new ArrayList<>(Collections.nCopies(size + 1, true));
        primes.add(2);

        for (long i = 0; i < size; ++i) {
            if (isPrime.get((int) i)) {

                long p = ((i * 2) + 3);
                primes.add((int) p);

                for (long j = ((i * i) * 2) + 6 * i + 3; j < size; j += p) {
                    isPrime.set((int) j, false);
                }
            }
        }

        return primes;
    }

}

class Backtrack {

    static void subsets(int[] nums, int idx, List<Integer> temp, List<List<Integer>> res) {
        res.add(new ArrayList<>(temp));
        for (int i = idx; i < nums.length; i++) {
            temp.add(nums[i]);
            subsets(nums, i + 1, temp, res);
            temp.remove(temp.size() - 1);
        }
    }

    static void permutations(int[] nums, List<Integer> temp, List<List<Integer>> res, boolean[] used) {
        if (temp.size() == nums.length) {
            res.add(new ArrayList<>(temp));
        }
        else {
            for (int i = 0; i < nums.length; i++) {
//                if (temp.contains(nums[i])) continue;
                if (used[i] || i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue; // if input has duplicates
                used[i] = true;
                temp.add(nums[i]);
                permutations(nums, temp, res, used);
                used[i] = false;
                temp.remove(temp.size() - 1);
            }
        }
    }

    static void sums(int[] nums, int idx, int target, List<Integer> temp, List<List<Integer>> res) {
        if (target < 0) return;
        if (target == 0) {
            res.add(new ArrayList<>(temp));
            return;
        }
        else {
            for (int i = idx; i < nums.length; i++) {
                temp.add(nums[i]);
                sums(nums, i, target - nums[i], temp, res); // i + 1 if elements cannot be reused
                temp.remove(temp.size() - 1);
            }
        }
    }

}

class DP {

    static int coins2D(int price, int[] C) {
        int[][] combos = new int[C.length][price + 1];

        for (int i = 0; i < C.length; ++i) {
            combos[i][0] = 1;
            for (int j = 1; j <= price; ++j) {
                int without = i - 1 >= 0 ? combos[i - 1][j] : 0;
                int with = j >= C[i] ? combos[i][j - C[i]] : 0;
                combos[i][j] = without + with;
            }
        }
        return (combos[C.length - 1][price]);
    }
    static int coinsTopDown(int price, int[] coins, int[] answer) {
        if (price < 0) return -1;
        if (price == 0) return 0;
        if (answer[price] != 0) return answer[price];

        int best = Integer.MAX_VALUE;
        for (int c: coins) {
            int res = coinsTopDown(price - c, coins, answer);
            if (res >= 0 && res < best) {
                best = 1 + res;
            }
        }

        if (best == Integer.MAX_VALUE) answer[price] = -1;
        else answer[price] = best;

        return answer[price];
    }
    static int coinsBottomUp(int price, int[] coins) {
        int[] answer = new int[price + 1];
        Arrays.fill(answer, price + 1);
        answer[0] = 0;
        for (int n = 1; n <= price; n++) {
            for (int coin: coins) {
                if (n - coin >= 0) answer[n] = Math.min(answer[n], answer[n-coin] + 1);
            }
        }
        return answer[price] > price ? -1 : answer[price];
    }

}