#P17712. [2026年江苏省队集训]PuBaBaOnO

[2026年江苏省队集训]PuBaBaOnO

题目描述

一年一度的 PuBaBa 杯开始了!

今年的 PuBaBa 杯总共有 nn 个选手来参加,编号分别为 1,2,⋯ ,n1,2,\cdots,n,他们的水平按编号依次递增,所以他们过的题目数量单调不降。

作为本场比赛的出题人,PuBaBa 总共出了 mm 道题,他希望第 ii 道题至少有 lil_i 个选手通过,至多有 rir_i 个选手通过,PuBaBa 预计所有题的过题人数和为 SS。

作为毒瘤出题人,PuBaBa 例行会在赛前举行“毒奶”活动。不过,PuBaBa 的毒奶是有依据的,他会计算每位选手最多过的题目数量。

不过,PuBaBa 有点太牛了,他决定将这个简单的任务交给您来完成。

输入格式

第一个,三个正整数 n,m,Sn,m,S 分别表示参赛选手,题目数量,以及总过题人数。

接下来 mm 行,每行两个正整数 li,ril_i,r_i 表示第 ii 道题至少有 lil_i 个选手通过,至多有 rir_i 个选手通过。

输出格式

若无解,输出 "-1"(不包含双引号)。

否则,为了压缩输出量,我们令 ansians_i 表示第 ii 个选手的最多过题数。

您仅需输出 ⨁i=1nansii\bigoplus_{i=1}^{n} ans_ii。

样例

大家觉得呢

输入 1

3 5 8
1 3
2 3
1 3
2 3
1 3

输出 1

5

解释

ansans 序列为 2,4,52,4,5。

输入 2

10 8 41
1 7
5 6
5 7
4 9
7 10
1 2
3 10
3 5

输出 2

50

解释

ansans 序列为 4,4,5,5,6,7,7,7,8,84,4,5,5,6,7,7,7,8,8。

更多样例请见下发文件。

提示

由于输入量很大,请使用快速的读入方式。

出题人为您准备了一份 fread 板子:https://www.luogu.com.cn/paste/xc3a5u5w。

测试点编号 n,m≤n,m\le 特殊性质
1∼21\sim 2 55 无
33 100100 保证 li=ril_i=r_i
4∼54\sim 5 无
6∼86\sim8 10001000 保证 li=ril_i=r_i
9∼109\sim 10 无
11∼1211\sim12 2×1052\times 10^5 保证 li=ril_i=r_i
13∼1413\sim14 10510^5 无
15∼1615\sim16 2×1052\times 10^5
17∼1817\sim18 5×1055\times 10^5
1919 2×1062\times10^6
2020 5×1065\times10^6

对于 100%100\% 的数据,保证 1≤n,m≤5×1061\le n,m \le 5\times 10^6,1≤li≤ri≤n1\le l_i\le r_i\le n,1≤S≤nm1\le S\le nm。

附加文件