curiosity2

# include <fstream>
# include <algorithm>
using namespace std;

#define NMax 100003
#define inf 2000000000

int Xf, N, D, T, Max;
pair <int, int> dp[NMax];

int main ()
{
    ifstream f("curiosity2.in");
    ofstream g("curiosity2.out");

    f >> Xf >> D >> T >> N;
    dp[1] = {0, -T};
    int st = 1, dr = 1;

    for (int i = 1; i <= N; ++i){

        int x, y, l;
        f >> x >> l; ///segmentul curent [x,y]
        y = x + l;

        ///verific daca segmentul citit poate aduce o maximizare
        int nr_max = 0, dist_min = inf;
        for (; st <= dr; ++st) { ///
            if (dp[st].second + T + D > y) break;

            int lung_seg = y - max (x, dp[st].second + T);
            int nr = lung_seg / D;

            int dist = max (x, dp[st].second + T) + nr * D;
            nr += dp[st].first;

            if (nr > nr_max || (nr == nr_max && dist_min > dist)) nr_max = nr, dist_min = dist;
        }

        if (st > 1) --st;

        if (Max < nr_max){
            dp[++dr] = {nr_max, dist_min};
            Max = nr_max;
        }
    }

    g << Max << '\n';

    return 0;
}