「REOI-p1」回忆

  出题人：LinkyChristian 文案：小糯米

“话虽如此，我们并没有四处游走让妖精一个一个地诞生。 只是在作为素材的巨大魂体上施予咒迹，好让她们带着接近人族的体格与人格自然诞生罢了。” 黄金妖精，自出生开始即刻下早夭诅咒之“人”，若非魔物无法抵御，是本不应在这茫茫尘世之中诞生之兵器。 每当前世之回忆涌上妖精之时，便是开启一朵含苞待放之花凋零倒计时之日。妖精的记忆，是由一条射线组成，为了便于叙述，我们不妨将射线当作数轴进行处理。在她们的记忆之中，会有若干个区间，在这个区间之内的回忆，是极易受到前世回忆的侵蚀的。但是由于生物的回忆本身自是不可探视分明之物，我们只能得知它们的 $m1$ 个开始区间 $[sl_i,sr_i]$ 与 $m2$ 个结束区间$[el_j,er_j]$ 。在这个回忆之内，会逐渐的有各种前世回忆涌出，侵蚀前期的记忆，当这些易于侵蚀的记忆区间全部被侵蚀殆尽后，黄金妖精便会就此“消失”。这些前世的回忆，可以看作成 $n$ 个不重叠的子段，这些子段的起点和终点恰好在一个开始区间和一个结束区间之内。而根据回忆的性质，不同的前世回忆的起点和终点自然是在不同的开始区间和结束区间内的。 记忆犹如湍急的小河，河水汩汩，顺流而下，搅动着石块与泥沙，不断地在水面上下浮沉。在上游之时，或许巉岩乱石，自有其沉重，因而水流清澈，自在澄明；越到入海口，石块逐渐的被泥沙所代替，哪怕只是微风逐浪，也会搅动其一片浑浊，将记忆都给摆弄的纠缠不清。每一次的记忆侵蚀，就如同翻腾的浪花，也许搅动的是泥沙，又或许只是将那些巨石推动了一隅。从数值上来叙述的话，第 $i$ 个起始区间被匹配能带来 $a_i$ 的贡献，第 $i$ 个结束区间被匹配能带来 $b_i$ 的贡献。当这些贡献达到了最大值，所谓的“侵蚀殆尽”，便会发生。那么现在这些妖精想知道，这个最大值究竟是多少。 特别的，如果数据本身无解，请输出 $-1$。 ------------ 简明题意： 给出 $m1$ 个开始区间 $[sl_i,sr_i]$ ，以及 $m2$ 个结束区间$[el_j,er_j]$ 。在数轴上选取不重叠的 $n$ 个子段，使得每个子段的起点和终点分别在一个开始区间和一个结束区间内。不同的子段的起点和终点需要在不同的开始区间和结束区间内。第 $i$ 个起始区间被匹配能带来 $a_i$ 的贡献，第 $i$ 个结束区间被匹配能带来 $b_i$ 的贡献。总贡献为选出的子段长度之和加上区间被匹配带来的贡献。求能最大总贡献是多少。 注意，将一个子段 $[l,r]$ 的长度定义为 $r-l$ ，这里的两个子段“重叠”定义为存在一个长度 > 0 的区间被同时包含在两个子段之内。 无解输出 $-1$。

第一行三个整数 $n,m1,m2$ 第二行 $2\times m1$ 个整数表示 $sl_1,sr_1,sl_2,sr_2,\dots , sl_{m1},sr_{m1}$， 第三行 $2\times m2$ 个整数表示 $el_1,er_1,el_2,er_2,\dots , el_{m2},er_{m2}$ 第四行 $m1$ 个数表示 $a_1,a_2,\dots ,a_{m1}$ 第五行 $m2$ 个数表示 $b_1,b_2,\dots ,b_{m2}$

输出一个整数，表示最大的总贡献。

2 2 2
1 3 7 8
4 5 9 10
0 0
0 0

7

2 3 3
1 2 3 5 100 200
5 7 9 10 400 500
1000 1000 0
1000 1000 0

4009

2 2 2
1 2 4 5
7 7 3 10
2 1
3 2

14

2 2 2
1 2 4 5
6 7 8 9
12 33
23 1

-1

对于第一组样例，将起始区间 $[1,3]$ 与结束区间 $[4,5]$ 匹配，选取子段 $[1,5]$ 长度为 $5-1=4$，再将起始区间 $[7,8]$ 与结束区间 $[9,10]$ 匹配，选取子段 $[7,10]$ 长度为 $10-7=3$ ，选取总长度为 $4+3=7$ ,满足起始区间与结束区间存在 $n$ 个匹配，且选取的子段没有重合，总贡献最大。 对于第二组样例，分别将 $[1,2]$ 与 $[9,10]$ ，$[3,5]$ 与 $[5,7]$ 匹配，选取子段 $[1,10]$ 和 $[5,5]$。 对于第三组样例，分别将 $[1,2]$ 与 $[3,10]$ ，$[4,5]$ 与 $[7,7]$ 匹配，选取子段 $[1,5]$ 和 $[5,7]$。 **subtask1:** 对于 $15\%$ 的数据，$n<=5,m1,m2<=10$。 **subtask2:** 对于 $100\%$ 的数据，$n,m1,m2<=100$ ，题目中所有数据 $\le 10^3$。