PAIR (VOI 2022)

#define task "PAIR"
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 2e3 + 5;

struct SegmentTree
{
    int n, st[N * 4];
    SegmentTree()
    {
        memset(st, 0, sizeof st);
    }

    void Update(int id, int l, int r, const int &x, const int &v)
    {
        if (l > x || r < x)
            return;
        if (l == x && r == x)
        {
            st[id] = v;
            return;
        }

        Update(id << 1, l, (l + r) / 2, x, v);
        Update(id << 1 | 1, (l + r) / 2 + 1, r, x, v);

        st[id] = max(st[id << 1], st[id << 1 | 1]);
    }

    void Update(int p, int v)
    {
        Update(1, 1, n, p, v);
    }

    int Get(int id, int l, int r, const int &a, const int &b)
    {
        if (l > b || r < a)
            return 0;
        if (l >= a && r <= b)
            return st[id];

        return max(Get(id << 1, l, (l + r) / 2, a, b), Get(id << 1 | 1, (l + r) / 2 + 1, r, a, b));
    }

    int Get(int l, int r)
    {
        return Get(1, 1, n, l, r);
    }
} f;

int n, d, a[N];
int dp[N * N];

vector<pair<int, int>> s, p;

void Read()
{
    cin >> n >> d;
    f.n = n;

    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    sort(a + 1, a + n + 1);
}

int Get(pair<int, int> x)
{
    return a[x.first] + a[x.second];
}

int Cal(int x, int y)
{
    p.clear();
    for (int i = x; i <= y; ++i)
        p.emplace_back(s[i]);

    sort(p.begin(), p.end(), [&](const pair<int, int> &x, const pair<int, int> &y)
         { return x.second < y.second || (x.second == y.second && x.first > y.first); });

    for (int i = 0, j = 0; i < (int)p.size(); ++i)
    {
        while (j < (int)p.size() && p[i].second == p[j].second)
            ++j;

        for (int t = i; t < j; ++t)
            dp[t] = f.Get(p[t].first + 1, p[t].second - 1) + 1;

        for (int t = i; t < j; ++t)
            f.Update(p[t].first, max(f.Get(p[t].first, p[t].first), dp[t]));

        i = j - 1;
    }

    for (int i = 0; i < (int)p.size(); ++i)
        f.Update(p[i].first, 0);

    return *max_element(dp, dp + p.size());
}

void Sub_3()
{
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
            s.emplace_back(i, j);

    sort(s.begin(), s.end(), [&](const pair<int, int> &x, const pair<int, int> &y)
         { return Get(x) < Get(y); });

    int ans(0);

    for (int i = 0, j = 0; i < (int)s.size(); ++i)
    {
        while (j < (int)s.size() && Get(s[i]) == Get(s[j]))
            ++j;

        ans = max(ans, Cal(i, j - 1));

        i = j - 1;
    }

    cout << ans;
}

void Sub_5()
{
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
            s.emplace_back(i, j);

    sort(s.begin(), s.end(), [&](const pair<int, int> &x, const pair<int, int> &y)
         { return Get(x) < Get(y); });

    int ans(0);

    for (int i = 0, j = 0, t = 0; i < (int)s.size(); ++i)
    {
        while (j < (int)s.size() && Get(s[i]) == Get(s[j]))
            ++j;
        while (t < (int)s.size() && Get(s[t]) - Get(s[i]) <= 1)
            ++t;

        ans = max(ans, Cal(i, t - 1));

        i = j - 1;
    }

    cout << ans;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }

    Read();

    if (d == 0)
        Sub_3();
    else
        Sub_5();
}