题目描述

译自 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.$