조개 줍기 timer 2초 memory 512MB

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 격자의 행(열)의 개수를 나타내는 정수 N(2≤N≤1,500)이 주어진다.

다음 N줄에는 각 격자 칸에서 주울 수 있는 조개의 개수가 제일 윗 행부터 순서대로 한 줄에 한 행씩 주어진다. 

한 행의 값은 가장 왼쪽 열의 값부터 하나씩 나열된다. 주어지는 값들은 0이상 1,000이하이다. 

다음 N개의 줄에는 각 줄에 변화 명령이 하나씩 주어진다. 변화 명령의 첫 글자는 U 혹은 D이다. 

이어서 빈칸을 하나 두고 두 자연수가 주어지는데, 첫 번째는 행 번호, 두 번째는 열 번호이다. 

첫 글자가 U인 경우 행 번호, 열 번호에 해당하는 격자 칸에서 주울 수 있는 조개의 개수가 1 증가한다. 

D인 경우 해당 격자 칸에서 주울 수 있는 조개의 개수가 1 감소한다. 감소한 결과가 음수가 되는 경우는 없다. 

각 변화에 대해서 아래에 지정한 값을 출력해야 한다. 주어진 각 변화 명령은 이전 변화들이 모두 적용된 결과에 적용된다.

표준 출력으로, 초기에 각 격자 칸의 입력을 기준으로 모든 지역에서 팔 수 있는 조개 개수의 최댓값의 합을 출력한다.

그 다음, 각 변화 명령 에 대해 그 변화 명령을 적용한 후, 모든 지역에서 팔 수 있는 조개 개수의 최댓값의 합을 출력 한다. 

전체 출력은 N+1줄임에 주의하라. 

[부분문제의 제약 조건]

● 부분문제 1: 전체 점수 100점 중 12점에 해당하며 N≤100 이다. 

● 부분문제 2: 전체 점수 100점 중 34점에 해당하며, 변화는 모두 D이고 출력의 첫 줄이 20,000,000이하인 입력만 주어진다. 

● 부분문제 3: 전체 점수 100점 중 54점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다.