做法是这样的。首先考虑小明和小李的区间在任意位置，然后我们在这个两个区间的中点的中点画一条线。可以得到，当活动区域的中点在这个中线一侧的时候，指派给中点所属那个人是最优的。 然后得到一个结论，当我们把活动区域按照中点排序之后，答案一定是某个前缀分给其中一个人，剩下的后缀分给另一个人。 然后考虑枚举 i ，怎么快速维护现在取了[1, i]的活动区域后，快速求出最优的那个负责区域的起点。我们直接维护A[x]表示负责区域起点为x的时候，[1, i]的活动区域跟x的交集贡献和，那只需要求max。那个点就是这个前缀要选的点。然后这个A[x]的维护，我们发现对于一条线段而言，它跟不同的起点的交集贡献是一个梯形一样的，就是先增大，然后相等，再降低，对应在数据结构上就是一个要支持区间加上一个等差数列一样的东西（即一次函数），并且要维护全局最大值。这里我们可以用分块维护，每个点维护一个a[i]，每个块维护一个k, d，这个块里的点的真实值是k * i + d + a[i]。如果整块加一个一次函数。就直接加上就可以了，散块的话就直接暴力维护。 现在问题变成了怎么快速求最大值。可以发现这个k * i + d + a[i]的最大值。我们可以这样维护，对于这个块维护一个凸包，每个点都是(i, a[i])。然后求最大值实际上相当于拿k这条斜率去切这个凸包。可以二分，然后区间加一次函数影响了k和d，但是k和d都不会影响这个凸包的形状。 构造凸包是线性的，查询是log的。所以理论复杂度可以做到O(nsqrt(nlogn))。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 4e18;

struct Line
{
    ll m, c;
    ll eval(ll x) const
    {
        return m * x + c;
    }
};

inline bool check_bad(const Line &l1, const Line &l2, const Line &l3)
{
    return (l2.c - l1.c) * (l3.m - l2.m) <= (l3.c - l2.c) * (l2.m - l1.m);
}

struct BHull
{
    int n;
    int B = 256;
    int num_blocks;
    vector<ll> a;
    vector<ll> blk_tag;
    vector<ll> blb_tag;
    vector<vector<Line>> cht;

    int get_block_idx(int i) const
    {
        return i / B;
    }

    int get_block_start(int block_idx) const
    {
        return block_idx * B;
    }

    int get_block_end(int block_idx) const
    {
        return min((block_idx + 1) * B - 1, n - 1);
    }

    void rebuild_cht(int block_idx)
    {
        int start = get_block_start(block_idx);
        int end = get_block_end(block_idx);
        ll m_tag = blk_tag[block_idx];
        ll c_tag = blb_tag[block_idx];

        for (int i = start; i <= end; ++i)
        {
            // A[i] = a[i] + m_tag * i + c_tag
            a[i] += m_tag * i + c_tag;
        }
        blk_tag[block_idx] = 0;
        blb_tag[block_idx] = 0;

        cht[block_idx].clear();
        for (int i = start; i <= end; ++i)
        {
            Line new_line = {(ll)i, a[i]};

            while (cht[block_idx].size() >= 2 &&
                   check_bad(cht[block_idx][cht[block_idx].size() - 2],
                             cht[block_idx].back(),
                             new_line))
            {
                cht[block_idx].pop_back();
            }
            cht[block_idx].push_back(new_line);
        }
    }

    ll cht_query(int block_idx) const
    {
        if (cht[block_idx].empty())
            return -INF;

        ll x = blk_tag[block_idx];

        int l = 0, r = cht[block_idx].size() - 1;

        while (l < r)
        {
            int mid = (r + l) >> 1;
            ll val1 = cht[block_idx][mid].eval(x);
            ll val2 = cht[block_idx][mid + 1].eval(x);

            if (val1 <= val2)
            {
                l = mid + 1;
            }
            else
            {
                r = mid;
            }
        }

        return cht[block_idx][l].eval(x) + blb_tag[block_idx];
    }

    ll get_real_value(int i) const
    {
        int block_idx = get_block_idx(i);
        return a[i] + blk_tag[block_idx] * i + blb_tag[block_idx];
    }

    BHull(int n) : n(n)
    {
        B = sqrt(n);
        B = 200;
        if (B == 0)
            B = 1;
        num_blocks = (n + B - 1) / B;

        a.resize(n, 0);
        blk_tag.resize(num_blocks, 0);
        blb_tag.resize(num_blocks, 0);
        cht.resize(num_blocks);

        for (int i = 0; i < num_blocks; ++i)
        {
            rebuild_cht(i);
        }
    }

    // add(l, r, k, b) 琛ㄧず a[i] += k * (i - l) + b
    void add(int l, int r, ll k, ll b)
    {
        l--;
        r--;

        int l_block = get_block_idx(l);
        int r_block = get_block_idx(r);

        if (l_block == r_block)
        {
            for (int i = l; i <= r; ++i)
            {
                a[i] += k * (i - l) + b;
            }
            rebuild_cht(l_block);
            return;
        }

        for (int i = l; i <= get_block_end(l_block); ++i)
        {
            a[i] += k * (i - l) + b;
        }
        rebuild_cht(l_block);

        for (int i = l_block + 1; i < r_block; ++i)
        {
            // 鍙樺寲閲? k * i + (b - k * l)
            // 鏂扮殑 blk_tag' = blk_tag + k
            // 鏂扮殑 blb_tag' = blb_tag + (b - k * l)
            blk_tag[i] += k;
            blb_tag[i] += b - k * l;
        }

        for (int i = get_block_start(r_block); i <= r; ++i)
        {
            a[i] += k * (i - l) + b;
        }
        rebuild_cht(r_block);
    }

    ll query(int l, int r)
    {
        l--;
        r--;

        int l_block = get_block_idx(l);
        int r_block = get_block_idx(r);
        ll max_val = -INF;

        if (l_block == r_block)
        {
            for (int i = l; i <= r; ++i)
            {
                max_val = max(max_val, get_real_value(i));
            }
            return max_val;
        }

        for (int i = l; i <= get_block_end(l_block); ++i)
        {
            max_val = max(max_val, get_real_value(i));
        }

        for (int i = l_block + 1; i < r_block; ++i)
        {
            max_val = max(max_val, cht_query(i));
        }

        for (int i = get_block_start(r_block); i <= r; ++i)
        {
            max_val = max(max_val, get_real_value(i));
        }
        return max_val;
    }
};
int n, m, k;
vector<ll> cal(const vector<pair<int, int>> &segs)
{
    BHull ds(n);
    vector<ll> pre(m);
    for (int i = 0; i < m; i++)
    {
        auto [l, r] = segs[i];
        int le_lo = max(1, l - k + 1);
        int le_up = min(n, r);
        int A, B;
        int Mins = 0;
        if (r - l + 1 >= k)
        {
            A = l;
            B = r - k + 1;
            Mins = k;
        }
        else
        {
            A = r - k + 1;
            B = l;
            Mins = r - l + 1;
        }
        if (max(A, le_lo) <= min(B, le_up))
        {
            ds.add(max(A, le_lo), min(B, le_up), 0, Mins);
        }
        if (max(le_lo, l - k + 1) <= min(A - 1, le_up))
        {
            int bx = Mins - 1 - (A - 1 - max(le_lo, l - k + 1));
            ds.add(max(le_lo, l - k + 1), min(A - 1, le_up), 1, bx);
        }
        if (max(le_lo, B + 1) <= min(le_up, r))
        {
            int bx = Mins - 1 - (max(le_lo, B + 1) - (B + 1));
            ds.add(max(le_lo, B + 1), min(r, le_up), -1, bx);
        }
        pre[i] = ds.query(1, n);
    }
    return pre;
}
void solve()
{
    cin >> n >> m >> k;
    vector<pair<int, int>> segs(m);
    for (auto &x : segs)
    {
        cin >> x.first >> x.second;
        assert(x.first <= x.second && x.first >= 1 && x.second <= n);
    }
    sort(segs.begin(), segs.end(), [](auto a, auto b)
         { return a.first + a.second < b.first + b.second; });
    auto pre = cal(segs);
    reverse(segs.begin(), segs.end());
    auto suf = cal(segs);
    reverse(suf.begin(), suf.end());
    ll ans = pre.back();
    for (int i = 0; i + 1 < m; i++)
    {
        ans = max(ans, pre[i] + suf[i + 1]);
    }
    cout << ans << "\n";
}
struct Timer {
    std::chrono::steady_clock::time_point start, end;
    std::chrono::duration<float> duration;

    Timer() {
        start = std::chrono::steady_clock::now();
    }

    ~Timer() {
        end = std::chrono::steady_clock::now();
        duration = end - start;
        float ms = duration.count() * 1000.0f;
        std::cerr << "Timer took " << ms << "ms\n";
    }
};

int main()
{
    Timer h;
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}