괄호문자열 만들기

다다스컴퍼니의 사원 따스는 길이가 $N$인 괄호 문자열을 만들려고 한다. 각 위치에는 여는 괄호 ( 또는 닫는 괄호 )를 하나씩 쓸 수 있다. $i$번째 위치에 (를 쓰면 $A_i$원, )를 쓰면 $B_i$원을 받는다. 따스가 받는 돈은 모든 위치에서 받는 돈의 합이다.

올바른 괄호 문자열은 다음 두 조건을 만족하는 문자열이다.

• 문자열 전체에서 여는 괄호와 닫는 괄호의 개수가 같다.
• 왼쪽부터 읽는 동안, 지금까지 읽은 닫는 괄호의 개수가 여는 괄호의 개수보다 많아지는 순간이 없다.

예를 들어 (), (()), ()()는 올바른 괄호 문자열이지만, )(와 (()는 그렇지 않다.

사장 다다스는 $M$개의 구간 $[l_j,r_j]$를 정했다. 따스가 만든 문자열에서 $l_j$번째부터 번째까지의 문자를 순서대로 떼어 내면, 그 문자열이 올바른 괄호 문자열이어야 한다. 이 조건을 모든 구간에서 동시에 만족해야 한다.

각 구간은 그 구간 안의 문자만으로 올바른지 판단한다. 구간 바깥의 괄호를 가져와 짝을 맞출 수 없다. 조건에 포함되지 않은 위치에도 괄호를 쓰고 돈을 받으며, 문자열 전체가 올바른 괄호 문자열일 필요는 없다.

모든 조건을 만족하면서 따스가 받을 수 있는 돈의 최댓값을 구하여라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 입력의 전체 형식은 다음과 같다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

각 테스트 케이스마다 모든 구간 조건을 만족할 때 받을 수 있는 돈의 최댓값을 한 줄에 출력한다.

• $1\leq T\leq100\ 000$.
• $2\leq N,M\leq200\ 000$.
• .