题目描述

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

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

这台超算的内存包含 $2^k$ 个存储单元，依次编号为 $0\ldots 2^k-1$。用内存段 $[L,R]$ 表示编号 $\ge L$ 且 $\le 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$ 个单元中存储的值为 $v_n$，$1\le v_i\le 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 \le k \le 30$，$1 \le n \le 10^5$，$1 \le m \le 10^9$。