Memory Assignment Minimization

An experimental laboratory is developing a new supercomputer that handles large-scale data. The computer has a memory consisting of \(2^k\) storage cells sequentially numbered from 0 to \(2^k - 1\). A memory segment \([L, R]\) denotes the cells with indices \(L \leq i \leq R\) and has length \(R - L + 1\).

A segment \([L,R]\) is called a correct memory segment if its length is a power of 2, say \(2^i\), and \(L\) is a multiple of \(2^i\). For example, when \(k = 3\), the correct memory segments are:

• \([0,7]\)
• \([0,3]\) and \([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]\)

Initially, every cell stores 0. The final configuration of memory is given in run-length encoded form. That is, you are given a sequence of pairs \((c_1, v_1), (c_2, v_2), \dots, (c_n, v_n)\) which means that the first \(c_1\) cells should be assigned the value \(v_1\), the next \(c_2\) cells the value \(v_2\), and so on. Note that \(\sum_{i=1}^{n} c_i = 2^k\) and \(1 \le v_i \le m\).

The only operation available is STORE([l,r], x), which assigns the value x to all cells in the correct memory segment \([l,r]\). Determine the minimum number of operations required to achieve the final configuration from the initial all-zero state.

Example: For \(k = 3\), \(n = 3\), \(m = 2\), run-length encoding c = {1, 2, 5} and v = {1, 2, 1}, the final memory configuration would be [1, 2, 2, 1, 1, 1, 1, 1].

Hint: You may use a divide and conquer strategy by noticing that the allowed segments form exactly the nodes of a complete binary tree. If a segment is uniform, then a single STORE can be applied over that segment.

inputFormat

The input consists of three lines:

1. The first line contains three integers \(k, n, m\) where \(2^k\) is the total number of memory cells, \(n\) is the number of segments in the run-length encoding, and \(m\) is the maximum possible value.
2. The second line contains \(n\) integers \(c_1, c_2, \dots, c_n\) representing the counts; their sum equals \(2^k\).
3. The third line contains \(n\) integers \(v_1, v_2, \dots, v_n\) representing the values for the corresponding segments.

outputFormat

Output the minimum number of STORE operations required to achieve the final configuration.

sample

3 3 2
1 2 5
1 2 1

5