35036번 - 코드배틀

문제

당신은 코드들이 싸운다고 하면 믿겠는가? NYPC 코드배틀은 주어진 게임 환경에서 승리할 수 있는 AI 코드를 개발해 대결하는 대회이다. 특히 이번 2025 NYPC 코드배틀 대회 결승의 경우, 게임 리플레이를 통해 두 코드의 전략이 어떻게 경기를 펼치는지를 보여주었으며, 짜릿한 역전승이 일어나 보는 이들의 흥미를 이끌었다.

이런 흥미진진한 시상식을 만들기 위해 NYPC 코드배틀 운영진은 여러 노력을 했으며, 그러한 노력 중 하나는 수많은 게임 로그 중 보는 이들이 가장 재미있어할만한 로그를 고르는 것이었다.

준겸이는 한쪽팀이 쭉 이기고 있는 모습이 역전의 기대감과 긴장감을 준다고 생각하여 다음과 같이 시상식에서 사용할 게임 로그를 선택하기 위한 점수 체계를 만들었다.

• 한 게임에서 A팀과 B팀이 총 $N$번 턴을 주고받는다.
• 게임 도중에 두 팀의 점수가 같아지는 일은 발생하지 않는다.
• $i$번째 턴이 끝났을 때 A팀이 이기고 있다면 흥미도가 $A_i$ 만큼, B팀이 이기고 있다면 $B_i$ 만큼 증가한다. (1ドル\le i\le N$)
• $x_j,y_j,z_j$턴이 각각 끝났을 때, 세 번 모두 한 팀이 이기고 있었다면 흥미도가 $c_j$ 만큼 증가한다. (1ドル\le j\le K$)
• $s_p$턴이 끝났을 때부터,$e_p$턴이 끝났을 때 까지 $t_p$ 팀이 계속해서 이기고 있었다면 흥미도가 $d_p$ 만큼 증가한다. (1ドル\le p\le Q$)

위의 방식으로 게임 로그의 점수를 매겼을 때, 이론상 얻을 수 있는 최대 흥미도를 구해보자.

입력

첫 번째 줄에 세 개의 정수 $N,ドル $K,ドル $Q$가 공백으로 구분되어 주어진다.

두 번째 줄에 $A_1,A_2,\cdots ,A_N$이 공백으로 구분되어 주어진다.

세 번째 줄에 $B_1,B_2,\cdots ,B_N$이 공백으로 구분되어 주어진다.

네 번째 줄부터 $K$개의 줄에 걸쳐, 그중 $j$번째 줄에는 $c_j,x_j,y_j,z_j$가 공백으로 구분되어 주어진다.

이후 $Q$개의 줄에 걸쳐, 그중 $p$번째 줄에는 $d_p,t_p,s_p,e_p$가 공백으로 구분되어 주어진다. $A$ 팀이 이겨야 한다면 $t_p=0,ドル $B$ 팀이 이겨야 한다면 $t_p=1$ 로 주어진다.

출력

이론상 얻을 수 있는 최대 흥미도를 출력한다.

제한

• 주어지는 모든 수는 정수이다.
• 3ドル\le N\le 500$
• 1ドル\le K,Q\le 500$
• 1ドル\le A_i,B_i\le 100,円(1\le i\le N)$
• 1ドル\le x_j,y_j,z_j\le N,円(1\le j\le K)$
• $x_j, y_j, z_j$는 서로 다르다. (1ドル \le j \le K$)
• 1ドル\le c_j\le 100,円(1\le j\le K)$
• 1ドル\le s_p\le e_p\le N,円(1\le p\le Q)$
• 0ドル\le t_p\le 1,円(1\le p\le Q)$
• 1ドル\le d_p\le 100,円(1\le p\le Q)$

노트