Description

For simplicity, the expression has a specific form: it consists of several subexpressions in parentheses, separated by the bitwise AND operator (denoted by $\&$). Each subexpression consists of one or more variables, separated by the bitwise OR operator (denoted by $|$). With this convention, the expression can be fully specified by giving the number of subexpressions and the number of variables in each subexpression. Variables are numbered only according to their occurrences in the expression.

For example, if the number of subexpressions is $4$, and the numbers of variables in each subexpression are $3$, $1$, $2$, $2$, then the expression is:

$$E=(v_1|v_2|v_3) \& (v_4) \& (v_5|v_6) \& (v_7|v_8)$$

Bitwise operators are defined in the usual way. For example, to compute $21 \& 6$, we first write the numbers (operands) in binary: $10101$ and $110$ (because $21=2^4+2^2+2^0$ and $6=2^2+2^1$). Each binary digit of the result now depends on the corresponding digits of the operands: if both operands have $1$, then the result digit is $1$, otherwise it is $0$. As shown on the left in the figure below, the result is $4$. If we want to compute $21| 6$, the process is the same, except that if the corresponding digit is $1$ in any operand, then the result is $1$. Therefore, the result digit is $0$ only when both operands have $0$. As shown in the middle of the figure below, the result is $23$. Extending this to more than two operands is straightforward. The example on the right below shows that $30 \& 11 \& 7=2$.

Input Format

The first line contains two positive integers $N$ and $P$. The second line contains $P$ positive integers ($K_1,K_2, \cdots ,K_P$), where $K_i$ is the number of variables in the $i$-th subexpression. Each $K_i$ is at least $1$, and their sum equals $N$. The next $N$ lines each contain two integers $A_j$ and $B_j$, specifying the value range of the $j$-th variable in the expression by $A_j \le v_j \le B_j$.

Output Format

One line containing one integer: the maximum value the expression can take.

8 4
3 1 2 2
2 4
1 4
0 0
1 7
1 4
1 2
3 4
2 3

6

Hint

Constraints

For $100 \%$ of the testdata, $1 \le N \le 100$, $1 \le P \le N$, $0 \le A_j \le B_j \le 2×10^9$.

Sample Explanation

The sample restricts the values of the eight variables in the expression as follows: $2 \le v_1 \le 4$, $1 \le v_2 \le 4$, $v_3=0$, $1 \le v_4 \le 7$, $1 \le v_5 \le 4$, $1 \le v_6 \le 2$, $3 \le v_7 \le 4$, and $2 \le v_8 \le 3$. If written in binary, one of the best assignments gives the expression $(100|011|000) \& (111) \& (100|010) \& (100|011)$. From this we can see that all subexpressions can become equal to $7$ except the third one.

Problem Notes

From Baltic Olympiad in Informatics 2006 Day 1:Bitwise.
Translated and organized by @求学的企鹅.

Translated by ChatGPT 5