1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;


struct OneSize
{
    vector<int32_t> m_vPatterns;

    int32_t m_iSize;
    int64_t m_iMaxScore;
};


static int n, c;

static int64_t iMaxScore;

static vector<OneSize> vSizes;

static int64_t aScores[500'002];


static void InitTable()
{
    for (int i = 1; i <= 500'000; ++i)
    {
        aScores[i] = 0;
    }
}


static void ReadData()
{
    int  iLastSize, a, w;

    cin >> n >> c;

    for (int i = 0; i < n; ++i)
    {
        cin >> a >> w;

        if (i == 0 || a != iLastSize)
        {
            OneSize os;

            os.m_iSize = a;
            os.m_iMaxScore = a;
            os.m_vPatterns.push_back(w);

            vSizes.push_back(os);
            iLastSize = a;
            continue;
        }

        vSizes.back().m_vPatterns.push_back(w);
    }
}


static void RemoveDuplicates(OneSize & os)
{
    std::ranges::sort(os.m_vPatterns);

    const auto [first, last] = std::ranges::unique(os.m_vPatterns);

    os.m_vPatterns.erase(first, last);
}


static void InitTheSmallestSize()
{
    OneSize & os = vSizes[0];

    iMaxScore = os.m_iSize;

    RemoveDuplicates(os);

    for (int32_t iPattern : os.m_vPatterns)
    {
        aScores[iPattern] = os.m_iSize;
    }
}


static void CalculateForBiggerSize(OneSize & osThis, const OneSize & osSmaller)
{
    RemoveDuplicates(osThis);

    osThis.m_iMaxScore = max(osThis.m_iMaxScore, osSmaller.m_iMaxScore);

    for (int32_t iPattern : osThis.m_vPatterns)
    {
        int64_t iCand0 = aScores[iPattern] + osThis.m_iSize;

        int64_t iCand1 = osThis.m_iSize + osSmaller.m_iMaxScore - c;

        int64_t iNewValue = max(iCand0, iCand1);

        aScores[iPattern] = iNewValue;

        if (iNewValue > osThis.m_iMaxScore)
        {
            osThis.m_iMaxScore = iNewValue;
        }

        if (iNewValue > iMaxScore)
        {
            iMaxScore = iNewValue;
        }
    }
}


static void Solve()
{
    InitTheSmallestSize();

    for (int i = 1; i < vSizes.size(); ++i)
    {
        CalculateForBiggerSize(vSizes[i], vSizes[i - 1]);
    }
}


int main()
{
    InitTable();

    ReadData();

    Solve();

    cout << iMaxScore;
}