홍익대학교 지하캠퍼스

홍익대학교 서울 캠퍼스의 건물들은 정문부터 후문까지 연결되어 있지만, 건물마다 연결되는 층이 제각각이다. 예를 들어 정문인 R동의 3층으로 나오면 K동의 1층이 있고, L동의 8층으로 나오면 I동의 1층이 있기도 하다. 캠퍼스가 작지만 복잡하게 이어져 있어서 학생들 사이에서는 '홍그와트'라는 별명으로 불린다.

건축공학과 학생인 기열이는 이런 특징이 잘 드러나도록 정문부터 후문까지 이어지는 홍익대학교 지하 캠퍼스를 설계하여 과제로 제출해야 한다. 그러나 기열이는 혼자 과제를 끝내기에는 시간이 턱없이 부족하다고 생각해서 포기하기 직전이다. 기열이를 도와주자.

기열이를 위해 유명한 건물 모델 사이트에서 M개의 모델을 가져왔다. 각 모델은 바로 3D프린터로 출력할 수 있으며, 모델들을 이어 붙이기만 하면 과제를 완성할 수 있다. 또한 모든 모델은 좌우로 뒤집어 사용할 수 있다. (단, 위아래가 바뀌도록 뒤집을 수는 없다.)

• 과제의 규격 때문에 지하 1층부터 지하 N층까지만 건물을 배치할 수 있다.
• 모든 건물은 양 옆면에 출입구가 한 개씩 있으며, 다른 건물과 연결될 때는 그림과 같이 출입구끼리 맞닿아야 한다.
• 각 모델에는 건물의 층 수 H_i, 출입구가 위치한 층 E_i1과 E_i2가 정해져 있다. 또한 해당 모델을 3D프린터로 출력하는 데 걸리는 시간 T_i가 주어진다.
• 같은 모델을 여러 번 사용할 수 있으며, 사용할 때마다 같은 시간이 든다.
• 정문의 R층과 후문의 D층에는 지하 캠퍼스와 연결되는 출입구가 있다. 이를 각각 시작점과 끝점으로 하여 홍익대학교 지하 캠퍼스를 설계한다.

모델의 높이는 바꿀 수 없지만 너비를 바꾸는 것은 매우 쉬우므로, 건물을 몇 개나 사용하는지는 중요하지 않다. 캠퍼스를 설계할 때 드는 최소 시간을 구해서 기열이에게 알려주자.

위와 같이 3개의 모델이 주어졌을 때, 각각 H, T, E1, E2의 값은 모델 아래 박스 안의 값과 같다.

N=9, R=3, D=2라고 할 때, 위 세 모델로 캠퍼스를 설계한다면 시간을 최소로 하는 설계 방법은 아래 그림과 같다.

이때 걸리는 시간은 38이다.

첫째 줄에는 건물을 배치할 수 있는 지하 층 수에 해당하는 자연수 N이 주어진다. (2 ≤ N ≤ 2,000)

둘째 줄에는 정문과 후문에 출입구가 위치한 층 R과 D가 공백을 사이에 두고 주어진다. (1 ≤ R ≤ N, 1 ≤ D ≤ N)

셋째 줄에는 모델의 개수 M이 주어진다. (1 ≤ M ≤ 2,000)

넷째 줄부터 M+3번째 줄까지 각 줄에는 모델의 층 수 H_i, 출력하는 데 걸리는 시간 T_i, 출입구가 있는 층 E_i1, E_i2가 공백을 사이에 두고 주어진다. (2 ≤ H_i ≤ N, 1 ≤ T_i ≤ 1,000,000, 1 ≤ E_i1 ≤ H_i, 1 ≤ E_i2 ≤ H_i, 단 E_i1 ≠ E_i2)

과제를 끝마치기 위해 필요한 최소 시간을 첫째 줄에 출력한다.

단, 주어진 모델로 캠퍼스를 설계할 수 없다면 첫째 줄에 -1을 출력한다.