색 타일 2

2018년에 국제 정보 올림피아드가 일본에서 열린다. 이를 기념하기 위해 IOI 위원회는 "약간 이상한 디자인"의 예술 작품을 만들어 대회장을 장식하려 한다. 위원회는 JOI (Just Odd Inventions) Co. Ltd.에 디자인을 의뢰했다. JOI의 디자이너들은 다음과 같이 제안했다.

• 작품은 H × W개의 칸으로 이루어진 직사각형 판 위에 만들어진다. 판을 N개의 타일로 덮는다. 타일은 서로 겹치지 않는다.
• 타일 i (1 ≤ i ≤ N)의 크기는 1 × 1 또는 1 × 2이다. 타일 i의 색은 Ci이다.
• 1 × 2 타일은 회전시켜 2 × 1 타일로 사용할 수 있다.

또한 그들은 작품에 사용할 타일의 종류를 제안했다. 그러나 디자인의 가장 중요한 부분인 판 위에 타일을 놓는 방법은 제안하지 않았다. JOI가 제안하는 디자인은 항상 아름답기 때문에, 위원회는 타일의 종류에 관한 JOI의 제안을 따르기로 했다. 위원회는 판 위에 타일을 놓는 방법을 고민해야 한다. 위원회는 디자인의 아름다움을 최대화하도록 타일을 놓기로 했다.

디자인의 아름다움은 다음과 같이 계산된다.

• 판 위에서 색 j인 타일과 색 k인 타일이 공유하는 칸의 변에 대해, 그 변의 점수는 Aj,k이다.
• 디자인의 아름다움은 판 위 칸들의 변 점수의 총합이다.

1 × 2 타일 두 개가 두 칸의 변을 공유하면, 이 두 변의 점수를 각각 독립적으로 센다. 아름다움이 최대가 되도록 판 위에 타일을 놓는 방법을 구해야 한다.

판의 크기, 각 타일의 크기와 색, 디자인의 아름다움을 계산하는 방법이 주어졌을 때, 아름다움이 최대가 되도록 타일을 놓는 방법을 구하라.

다섯 개의 부분 문제가 있다. 각 부분 문제는 하나의 공개 입력 데이터에 대응한다. 각 입력 데이터 파일의 형식은 다음과 같다.

• 입력의 첫째 줄에는 네 개의 정수 H, W, K, N이 공백으로 구분되어 주어진다. 이는 직사각형 판이 H × W개의 칸으로 이루어져 있고, 타일의 색 종류가 K가지이며, 디자인에 N개의 타일이 사용됨을 의미한다.
• 다음 N개의 줄 중 i번째 줄 (1 ≤ i ≤ N)에는 두 개의 정수 Si, Ci가 공백으로 구분되어 주어진다. 이는 타일 i의 크기가 1 × Si이고 색이 Ci임을 의미한다.
• 다음 K개의 줄 중 j번째 줄 (1 ≤ j ≤ K)에는 K개의 정수 Aj,1, Aj,2, . . . , Aj,K가 공백으로 구분되어 주어진다. 이는 색 j인 타일과 색 k인 타일이 변을 공유할 때 점수가 Aj,k임을 의미한다.

각 입력 데이터 파일에 대응하는 출력 데이터 파일을 제출하라. 출력 데이터 파일은 N개의 줄로 이루어진다. i번째 줄 (1 ≤ i ≤ N)은 타일 i를 판 위에 놓는 방법을 다음 형식으로 나타낸다.

• Si = 1일 때, i번째 줄에는 두 개의 정수 Ai, Bi가 공백으로 구분되어 있어야 한다. 이는 타일 i가 위에서 Ai번째 행, 왼쪽에서 Bi번째 열에 있는 칸에 놓임을 의미한다.
• Si = 2일 때, i번째 줄에는 네 개의 정수 Ai, Bi, Ci, Di가 공백으로 구분되어 있어야 한다. 이는 타일 i가 위에서 Ai번째 행, 왼쪽에서 Bi번째 열에 있는 칸과 위에서 Ci번째 행, 왼쪽에서 Di번째 열에 있는 칸을 덮도록 판 위에 놓임을 의미한다.

모든 입력 데이터는 다음 조건을 만족한다.

• 1 ≤ H ≤ 100.
• 1 ≤ W ≤ 100.
• 1 ≤ K ≤ 100.
• 1 ≤ N ≤ 10 000.
• 1 ≤ Si ≤ 2 (1 ≤ i ≤ N).
• 1 ≤ Ci ≤ K (1 ≤ i ≤ N).
• H × W = S1 + S2 + . . . + SN.
• 0 ≤ Aj,k ≤ 1 000 (1 ≤ j ≤ K, 1 ≤ k ≤ K).
• Aj,k = Ak,j (1 ≤ j ≤ K, 1 ≤ k ≤ K).

이 샘플 입력에서 디자인의 판 크기는 3 × 2이고, 4개의 타일이 사용된다. 각 타일의 색과 크기는 다음과 같다.

색 1인 1 × 1 타일, 색 2인 1 × 2 타일, 색 3인 1 × 1 타일, 색 1인 1 × 2 타일이 있다.

타일을 다음과 같이 놓는다. 그림의 숫자는 타일의 번호를 나타낸다.

디자인의 아름다움은 다음과 같이 계산된다. 디자인의 아름다움은 26이다.

• 색 2인 타일 2와 색 1인 타일 4가 변을 공유하므로 점수 7을 얻는다.
• 색 2인 타일 2와 색 1인 타일 1이 변을 공유하므로 점수 7을 얻는다.
• 색 1인 타일 4와 색 1인 타일 1이 변을 공유하므로 점수 2를 얻는다.
• 색 1인 타일 4와 색 3인 타일 3이 변을 공유하므로 점수 5를 얻는다.
• 색 1인 타일 1과 색 3인 타일 3이 변을 공유하므로 점수 5를 얻는다.