Problem Description

Given two arrays \(a\) and \(b\) each of length \(n\), merge them to form an array \(c\) of length \(2 \times n\).

Let the \(i\)-th element of array \(a\) be placed at the \(lb_i\)-th position in array \(c\) after merging, and the \(i\)-th element of array \(b\) be placed at the \(lc_i\)-th position in array \(c\). The merging must satisfy: \(lb_1 < lb_2 < ... < lb_{n-1} < lb_n\) and \(lc_1 < lc_2 < ... < lc_{n-1} < lc_n\), i.e., the relative positions of elements in both arrays remain unchanged.

After merging, you need to perform the following operations on array \(c\):

1. Transformation Operation: Select an interval \([l, r]\). For each \(i \in [l, r]\), if \(c_i\) is \(y\), change it to a number different from \(y\); otherwise, change it to \(y\).
2. Reversal Operation: Select an interval \([l, r]\) and reverse the numbers in this interval. This operation must be performed exactly \(z\) times.

Output the minimum number of transformation operations required to make all elements in array \(c\) equal to \(y\).

Input Format

The first line contains three integers \(n\), \(y\), and \(z\).

The second line contains \(n\) integers representing the elements of array \(a\).

The third line contains \(n\) integers representing the elements of array \(b\).

Output Format

A single integer representing the answer.

Sample Input and Output

Sample Input #1

5 1 1
1 1 45 1 4
1 9 1 9 810

Sample Output #1

1

Sample Input #2

20 0 3
1 0 0 8 6 10 0 8 6 1 0 0 86 1 0 0 8 6 0 0
5 2 0 1 3 1 4 52 0 13 14 0 1 0 1 0 4 0 5 0

Sample Output #2

4

Sample Input #3

3 2 4
110 105 117
99 108 98

Sample Output #3

1

Notes/Hints

[Sample Explanation]

For Sample #1, let \(c\) be \(\{1,1,1,9,45,1,1,9,4,810\}\).

Where \(c_1=a_1, c_2=b_1, c_3=a_2, c_4=b_2, c_5=a_3, c_6=a_4, c_7=b_3, c_8=b_4, c_9=a_5, c_{10}=b_5\). This satisfies the requirements.

Then reverse the interval \([4,7]\), changing \(c\) to \(\{1,1,1,1,1,45,9,9,4,810\}\).

Next, perform the transformation operation to change all numbers in \([6,10]\) to \(1\).

Thus, only one transformation operation is needed, and it can be proven that no better strategy exists.

[Data Constraints]

Please note the special time limits and use faster IO methods.

This problem uses bundled testing.

Special Condition A: Both arrays contain only elements equal to \(y\) or none equal to \(y\).

For all data, \(0 \leqslant y, z \leqslant 10^9\), and all input data are within the int range.

见题面 Input 部分

见题面 Output 部分