A new supercomputer architecture is being developed in a scientific laboratory,
allowing efficient processing of large amounts of data.
The supercomputer has 2k memory cells, numbered from 0 to 2k– 1. Segment
[L, R] is a sequence of consecutive memory cells with numbers from L to R,
inclusive.
Some memory spans are correct. The memory span [L, R] is the
correct if its length (R – L + 1) is equal to 2i for some i, and the number L is divisible by 2i.
For example, if k = 3, then the memory cells are numbered from 0 to 7, and the correct ones are
segments [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] and [7, 7].
The key operation in the new architecture is the STORE operation, which in one
action assigns the same value to all memory locations of some valid
segment.
Initially, all memory cells contain the value 0. The laboratory plans to run
data processing program on the supercomputer, but before running it, you need
initialize the memory in a certain way. Namely: the first c1 memory cells
must be filled with v1 values, the following c2 cells — v2 values, and so on,
the last cn memory cells must be filled with values vn, where 1 ≤ vi ≤ m.
Scientists need to figure out what is the minimum number of STORE operations needed
execute to initialize the memory as required.
For example, if k = 3, n = 3, m = 2, c1 = 1, v1 = 1, c2 = 2, v2 = 2, c3 = 5, v3 = 1, then the final
the contents of memory should be: [1, 2, 2, 1, 1, 1, 1, 1]. In this case for
three STORE operations are enough to initialize the memory:
- STORE([0, 7], 1), after this operation all memory cells contain the value 1;
- STORE([1, 1], 2), after this operation, the contents of the memory [1, 2, 1, 1, 1, 1, 1, 1];
- STORE([2, 2], 2) , after this operation the contents of the memory are [1, 2, 2, 1, 1, 1, 1, 1],
as required.
Note that the STORE([1, 2], 2) operation cannot be performed because [1, 2] is not a
is a valid chunk of memory.
It is required to write a program that, given the contents of memory
defines the minimum number of STORE operations to be performed for the
memory initialization in the given way.
Input data format
The first line of the input contains three integers: k, n and m (0 ≤ k ≤ 30,1 ≤ n ≤ 10
5.1 ≤ m ≤ 109).
The next n lines contain two integers each, the i-th of these lines contains numbers ci
and vi (1 ≤ ci ≤ 2k, 1 ≤ vi ≤ m, c1 + c2 + … + cn = 2k).
Output format
It is required to output a single integer – minimum number of STORE operations,
which must be performed to initialize the memory in a given way.