히어로 파워

올해 10월은 리듬 게임의 달이다. 큰 작품 두 개가 같은 달에 나온다. Bj0rn은 그중 새로 나온 쪽에서 순위표 1위를 노리고 있는데, 새 곡마다 최대 점수가 몇 점인지 계산하는 데 도움이 필요하다. 새 게임에는 히어로 파워라는 것이 있고, Bj0rn은 이것이 예전부터 이런 게임에 있던 스타 파워와 같은 물건이라고 본다.

점수 규칙은 이렇다. 플레이어는 노트 차트를 따라 진행하면서 노트를 하나 칠 때마다 1점을 얻는다. Bj0rn은 완벽 말고는 만족하지 않으므로 모든 노트를 다 친다.

여기에 스타 파워, 줄여서 SP가 더해진다. 차트에는 별 모양 노트가 이어지는 구간이 군데군데 나오고, 이런 구간을 SP 구간이라고 한다. SP 구간의 첫 노트와 마지막 노트 사이에 있는 동안 플레이어는 SP 게이지를 충전할 수 있다. 게이지에는 충전에 쓴 시간이 쌓인다. 충전은 첫 노트의 순간부터 시작할 수 있고 마지막 노트까지 이어갈 수 있다. 도중에 언제든 멈출 수 있고 쌓인 SP를 바로 쓰지 않아도 되므로, 여러 구간에서 충전한 양을 모을 수 있다.

게이지에 시간이 조금이라도 쌓여 있으면 곡의 어느 지점에서든, 노트와 정확히 같은 순간에도 스타 파워를 발동할 수 있다. 발동한 순간부터 게이지는 완전히 빌 때까지 줄어든다. 게이지에 $\pi + \sqrt[4]{7}$ 밀리초가 쌓여 있으면 다 비우는 데 $\pi + \sqrt[4]{7}$ 밀리초가 걸린다. 발동 중에는 게이지가 비어 있지 않은 동안 모든 노트가 2점이다. 발동하는 순간과 정확히 같은 위치의 노트는 이미 2점이고, 게이지가 비는 바로 그 순간의 노트는 1점이다.

발동에는 대가가 따른다. 발동 구간이 SP 구간과 겹치고 그 겹치는 동안 게이지가 양수인 지점이 있으면, 그 SP 구간은 평범한 노트로 돌아간다. SP 구간의 첫 노트를 게이지가 0이 되는 바로 그 순간에 치면 그 구간은 사라지지 않는다. SP 구간 한가운데서 발동해도 되지만, 그 구간의 남은 부분은 겹침 때문에 사라지므로 거기서 스타 파워를 더 충전하지 못한다.

Bj0rn에게 가장 좋은 전략을 찾아 몇 점을 얻는지 구하라.

첫째 줄에 노트의 개수 $n$과 SP 구간의 개수 $p$가 주어진다 ($1 \le n \le 50\,000$, $0 \le p \le 100$). 둘째 줄에 노트의 위치를 밀리초 단위로 나타낸 정수 $n$개가 증가하는 순서로 주어진다 ($0 \le t_i \le 50\,000\,000$). 이어지는 $p$개의 줄에는 $i$번째 SP 구간의 시작 위치와 끝 위치를 나타내는 두 정수 $s_i$와 $e_i$가 주어진다 ($0 \le s_i < e_i \le 50\,000\,000$).

모든 SP 구간은 시작 위치와 끝 위치에 노트가 있다. SP 구간끼리는 서로 겹치지 않고, 오름차순으로 주어진다.

최대 점수를 정수 하나로 출력한다.