#3029. 「ROIR 2018 Day2」大数据处理

内存限制:512 MiB 时间限制:1500 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: Planet6174

题目描述

译自 ROI 2018 Regional. Day2 T4. Обработка больших данных

某实验室正在研发一种能处理大规模数据的新型超级计算机。

这台超算的内存包含 2^k 个存储单元,依次编号为 0\ldots 2^k-1. 用内存段 [L,R] 表示编号 ≥L ≤R 的所有存储单元,该内存段的长度为 R-L+1.

定义:如果内存段 [L,R] 的长度是 2 的整数次幂(不妨假设是 2^i ),且 L 2^i 的整数倍,那么这个内存段是「正确的内存段」。

k=3, 则正确的内存段为 [0,7], [0,3], [4,7], [0,1], [2,3], [4,5], [6,7], [0,0], [1,1], [2,2], [3,3], [4,4], [5,5], [6,6] [7,7].

现在,每个存储单元所存储的值均为 0. 你需要给每个存储单元赋值。简单起见,我们用游程编码的形式给出每个单元上的值。开头的 c_1 个单元中存储的值为 v_1, 接下来 c_2 个单元中存储的的值为 v_2, 以此类推,最后的 c_n 个单元中存储的值为 c_n, 1≤v_i≤m.

举个例子,如果 k = 3, n = 3, m = 2, c = \{1, 2, 5\}, v = \{1, 2, 1\}, 那么内存将被赋值为 [1, 2, 2, 1, 1, 1, 1, 1].

你只有一种方法给单元赋值: \mathtt{STORE}([l,r],x). 该函数表示将内存段 [l,r] 中所有单元全部赋值为 x. 注意, [l,r] 必须是合法的内存段。

试求至少需要多少次操作才能达成要求。

输入格式

第一行三个整数 k,n,m
接下来的 n 行,每行三个整数 c_i,v_i

输出格式

输出一行一个整数,表示至少的次数。

样例

样例输入

3 3 2
1 1
2 2
5 1

样例输出

3

样例解释

目标: [1, 2, 2, 1, 1, 1, 1, 1]

  • \mathtt{STORE}([0, 7], 1), 得到 [1, 1, 1, 1, 1, 1, 1, 1];
  • \mathtt{STORE}([1, 1], 2), 得到 [1, 2, 1, 1, 1, 1, 1, 1];
  • \mathtt{STORE}([2, 2], 2), 得到 [1, 2, 2, 1, 1, 1, 1, 1].

数据范围与提示

0 ≤ k ≤ 30, 1 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^9.

子任务编号 分值 k\le k\le m\le
1 15 3 8   8  
2  15  19 10
3 15
4 10 50
5 15 19
6 30