비트 연산식

시간 제한1초메모리 제한128 MB

요약

각 변수의 범위가 주어지고 그룹 내에서는 OR, 그룹 간에는 AND로 결합된 비트 표현식이 가질 수 있는 최댓값을 구합니다.

난이도: 보통10점 중 7점
유형: 비트 연산, 그리디, 수학
정답자: 아직 제출이 없습니다

문제

신호 처리에서는 각 변수가 주어진 범위의 정수일 때, 비트 AND과 OR 연산자로 이루어진 식이 가질 수 있는 최댓값이 필요할 때가 있습니다. 이러한 식과 각 변수의 범위를 입력받아, 식이 가질 수 있는 최댓값을 구하는 프로그램을 작성하세요.

식의 형태는 항상 동일합니다. 여러 개의 부분식을 각각 괄호로 묶고 비트 AND 연산자(&)로 연결합니다. 각 부분식은 하나 이상의 변수를 비트 OR 연산자(|)로 연결한 것입니다. 이 형태 덕분에, 부분식의 개수와 각 부분식이 포함하는 변수의 개수만으로 식 전체를 완전히 나타낼 수 있습니다. 변수는 식에 나타나는 순서대로 번호가 매겨집니다.

예를 들어 부분식이 4개이고 각각 3, 1, 2, 2개의 변수를 포함하면 식은 다음과 같습니다.

E = (v1 | v2 | v3) & (v4) & (v5 | v6) & (v7 | v8)

비트 연산자는 통상적인 방식으로 동작합니다. 21 & 6을 계산하려면 두 수를 이진수 10101과 00110으로 쓰고, 결과의 각 자리는 두 피연산수 모두 1일 때만 1이 되어 00100 = 4가 됩니다. 21 | 6은 두 피연산수 중 적어도 하나가 1이면 결과 자리가 1이 되어 10111 = 23이 됩니다. 이 규칙은 세 개 이상의 피연산수에도 그대로 확장됩니다. 예를 들어 30 & 11 & 7 = 2입니다.

                    11110
  10101    10101    01011
& 00110  | 00110  & 00111
-------  -------  -------
  00100    10111    00010

입력

첫째 줄에 두 정수 N과 P가 주어집니다. N은 변수의 총 개수(1 ≤ N ≤ 100), P는 부분식의 개수(1 ≤ P ≤ N)입니다. 둘째 줄에는 P개의 정수 K1 … KP가 주어지며, Ki는 i번째 부분식에 포함된 변수의 개수입니다. 모든 Ki는 1 이상이고 그 합은 N과 같습니다. 이어지는 N개의 줄에는 각각 두 정수 Aj와 Bj(0 ≤ Aj ≤ Bj ≤ 2 000 000 000)가 주어지며, 이는 j번째 변수의 범위 Aj ≤ vj ≤ Bj를 나타냅니다.

출력

식이 가질 수 있는 최댓값을 한 줄에 정수 하나로 출력합니다.

힌트

위 식에서 범위가 2 ≤ v1 ≤ 4, 1 ≤ v2 ≤ 4, v3 = 0, 1 ≤ v4 ≤ 7, 1 ≤ v5 ≤ 4, 1 ≤ v6 ≤ 2, 3 ≤ v7 ≤ 4, 2 ≤ v8 ≤ 3이라고 합시다. 한 최적 할당에서는 세 번째 부분식을 제외한 모든 부분식이 7에 도달할 수 있지만 세 번째 부분식은 7에 도달할 수 없으므로, 부분식들의 AND, 즉 답은 6이 됩니다.

예제8

예제 1

입력

예상 출력

예제 2
입력
```
1 1
1
0 0
```
예상 출력
```
0
```
예제 3
입력
```
1 1
1
5 10
```
예상 출력
```
10
```
예제 4
입력
```
2 1
2
4 4
1 1
```
예상 출력
```
5
```
예제 5
입력
```
2 1
2
4 4
1 4
```
예상 출력
```
7
```
예제 6
입력
```
6 2
3 3
2 4
1 4
0 0
1 7
1 4
1 2
```
예상 출력
```
7
```
예제 7
입력
```
3 1
3
4 4
2 2
1 1
```
예상 출력
```
7
```
예제 8
입력
```
1 1
1
0 2000000000
```
예상 출력
```
2000000000
```