Minimum Transformation Operations After Merging Arrays

You are given two arrays a and b of length n. You must merge them into an array c of length 2n while preserving the relative order of elements in each array. Formally, if after merging the i-th element of array a is placed at position \(lb_i\) in c and the i-th element of array b is placed at position \(lc_i\) in c, then it must hold that \[ lb_1 < lb_2 < \cdots < lb_n \quad \text{and} \quad lc_1 < lc_2 < \cdots < lc_n. \]

After merging, you are allowed to perform the following two operations on array c:

1. Transformation Operation: Choose an interval \([l,r]\). For each index \(i\) in \([l,r]\), if \(c_i = y\) then change it to some number different from \(y\), otherwise change it to \(y\). In other words, this operation toggles the state of each element relative to \(y\).
2. Reversal Operation: Choose an interval \([l,r]\) and reverse the elements within that interval. This reversal operation must be performed exactly \(z\) times (throughout the process).

Your goal is to make every number in c equal to \(y\) while using as few transformation operations as possible. Note that the reversal operations do not change whether an element is equal to \(y\) (they only reverse the order), so they can be performed on intervals that already consist solely of \(y\) without harming the current state.

Hint: If we define a binary state for each element of c as follows:

[ \text{state} = \begin{cases} 1, & \text{if } c_i = y,\ 0, & \text{if } c_i \neq y, \end{cases} ]

then applying a transformation operation toggles the state in a selected interval. Without any reordering, the optimal way to convert all 0's (i.e. elements not equal to \(y\)) to 1's is to toggle each contiguous segment of 0's exactly once. Since you can choose the merge ordering arbitrarily (subject to the relative ordering constraints within a and b), you may arrange the elements to group as many 0's together as possible. The minimal number of transformation operations required is therefore equal to the minimum number of contiguous blocks of 0's you can obtain in the merged array c under an optimal interleaving of the two arrays.

Input/Output Note: The parameter \(z\) is provided to force you to use the reversal operation exactly \(z\) times. However, by choosing the segment for the reversal operation carefully (for example, a segment containing only \(y\)), you can ensure that the reversals do not affect the state of any element with respect to \(y\). The main challenge is thus to determine the optimal interleaving of the two arrays to minimize the number of contiguous segments of values not equal to \(y\), and hence minimize the number of transformation operations.

inputFormat

The first line contains three integers n, z and y (1 ≤ n ≤ 500, 0 ≤ z ≤ 10, and y is an integer). The next line contains n integers representing the array a. The third line contains n integers representing the array b.

Each integer in the arrays can be any 32-bit signed integer.

outputFormat

Output a single integer, which is the minimum number of transformation operations required to make every element of the merged array c equal to \(y\) after exactly \(z\) reversal operations have been executed (the reversal operations can be performed on intervals that do not affect the transformation result).

sample

2 0 1
1 0
0 1

1