#1909. 新居规划

    ID: 1909 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1963来源:qoj.ac数据:公开样例动态规划

新居规划

新居规划

题目描述

标题: 新居规划 - Problem - QOJ.ac

#10307. 新居规划

Statistics

随着苏州的建设与发展,越来越多人选择来到苏州开始新生活。

在一片新建的小区里,有 m 栋围成一圈的房子,房子从 1 到 m 编号,房子 i 与 房子 i+1 相邻,特别地,房子 1 和房子 m 也相邻。

小 Z 需要为 n 个人安排住宿,对于第 i 个人来说:

  • 如果 i 没有被安排住宿,那么他的满意度是 0;
  • 如果 i 被安排了住宿,那么他的满意度是 ai;
  • 如果 i 被安排了住宿且其拥有邻居(即他的某个相邻房子也被安排了住宿),那么他的满意度额外加 bi(也即总满意度为 ai+bi)。

小 Z 希望每个被安排了住宿的人都住进不同的房子,现在他想知道怎么样安排才能最大化所有人的总满意度。

输入格式

从标准输入读入数据。

本题的测试点包含有多组测试数据

输入的第一行包含两个整数 s 和 t,分别表示子任务编号和测试数据组数。对于样 例,s 表示该样例与子任务 s 拥有相同的限制条件。

接下来,对于每组测试数据:

  • 输入第一行包含两个整数 n,m,表示人数和房子数。
  • 接下来 n 行,每行包含两个整数 ai,bi,意义如题面所述。

输出格式

输出到标准输出。

每组数据输出一行一个整数,表示最大的总满意度。

样例

输入

8 5
2 2
70 63
55 63
7 7
-18 10
-8 -14
-20 -3
-2 -13
22 -40
15 -34
17 -39
4 1
-42 49
24 15
-27 43
-22 2
2 2
-17 23
12 -18
4 4
3 -42
3 -16
54 -10
51 -57

输出

251
54
39
12
105

样例二

见下载目录下的 ex_2.in 与 ex_2.ans。

该组样例满足子任务 4 的条件。

样例三

见下载目录下的 ex_3.in 与 ex_3.ans。

该组样例满足子任务 7 的条件。

样例四

见下载目录下的 ex_4.in 与 ex_4.ans。

该组样例满足子任务 8 的条件。

子任务

对于所有测试数据,保证 1≤t≤10,1≤n≤2×105,0≤m≤109,−109≤ai,bi≤109。

​

子任务得分n≤特殊性质1515无22031550041035255×1046202×10575A810B

特殊性质 A:∀1≤i≤n,ai≤0;

特殊性质 B:∀1≤i≤n,ai≥0。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

8 5
2 2
70 63
55 63
7 7
-18 10
-8 -14
-20 -3
-2 -13
22 -40
15 -34
17 -39
4 1
-42 49
24 15
-27 43
-22 2
2 2
-17 23
12 -18
4 4
3 -42
3 -16
54 -10
51 -57
251
54
39
12
105