근처에 붙어있는 KOI 고등학교와 IOI 고등학교 학생들이 파티를 열었다.

이 파티에는 KOI 고교에서 A명, IOI 고교에서 B명이 참석한다.

각 고등학교의 학생들은 이름 순서대로 1~A, 1~B의 서로 다른 번호로 구분된다.

두 고등학교 사이에는 N개의 연합 동아리가 있다.

i번째 동아리에는 KOI 고등학교의 a_i번 학생부터 b_i번 학생, IOI 고등학교의 c_i번 학생부터 d_i번 학생이 소속되어 있다.

그리고 이 동아리의 활동 점수는 e_i다.

파티에서 게임을 하나 진행하기로 했다.

무대 위에는 KOI 고등학교의 C번 학생이 올라와 있다.

아직 무대에 올라오지 않은 학생들은 무대 위의 학생과 같이 소속된 동아리가 있다면 무대로 올라가고 그 동아리의 활동 점수 만큼을 얻을 수 있다.

점수의 계산은 무대 위의 학생과 겹치는 동아리들 중 최댓값의 활동 점수 만을 세는 것이다.

게임은 위의 규칙에 따라 한 학생씩 무대 위로 올리면서 모든 학생이 올라갈 때까지 진행된다.

이때 올릴 수 있는 학생이 여러 명이라면 지금 올려서 얻을 수 있는 점수가 가장 큰 학생을 올리고, 점수가 같다면 KOI 고등학교 학생을 먼저, 고등학교까지 같다면 번호가 작은 학생을 먼저 올린다.

우리는 게임이 잘 진행되었을 때 학생들이 무대 위로 올라가며 얻는 점수의 총합이 궁금해졌다.

파티 timer 3000초 memory 512MB

파티 3000초 512MB