도서관

무인도에 홀로 표류한 로빈슨 크루소가 살고 있다. 어느 날 왕실 도서관을 싣고 가던 배가 근처에서 난파했다. 로빈슨은 늘 그랬듯 쓸 만한 물건을 섬으로 옮겨 왔고, 이번에는 책이 가득 든 커다란 궤짝을 가져왔다.

로빈슨은 이 책들을 꽂을 책장을 만들기로 했다. 바위에 직사각형 벽감(niche)을 파고, 나무 못을 박은 뒤, 같은 높이에 있는 못 두 개마다 그 위에 나무 판자를 걸쳐 놓았다. 그래서 모든 판자는 수평이 되어 선반 역할을 한다.

그런데 유난히 오래되고 큰 책 한 권이 책장에 들어가지 않았다. 로빈슨은 그 책의 높이와 너비를 재고, 다른 선반들의 위치와 벽감의 크기를 고려하여, 그 책이 어느 한 선반 위에 완전히 놓이도록 책장을 다시 설계하기로 했다. 각 선반에는 다음 여섯 가지 연산 중 정확히 하나를 적용할 수 있다.

1. 선반을 원래 자리에 그대로 둔다.
2. 선반을 왼쪽이나 오른쪽으로 옮긴다.
3. 판자의 일부를 잘라 선반을 짧게 만들고, 필요하면 왼쪽이나 오른쪽으로 옮긴다.
4. 두 못 중 하나를 같은 높이의 다른 위치로 옮기고, 선반을 왼쪽이나 오른쪽으로 옮긴다.
5. 판자의 일부를 잘라 선반을 짧게 만들고, 두 못 중 하나를 같은 높이의 다른 위치로 옮긴 뒤, 필요하면 짧아진 선반을 왼쪽이나 오른쪽으로 옮긴다.
6. 선반을 그것을 받치는 두 못과 함께 통째로 제거한다.

어떤 선반이 서로 다른 두 못으로 받쳐지고, 그 선반의 중심이 두 못 사이에 있거나 둘 중 하나와 겹칠 때, 그 선반은 두 못에 의해 올바르게 받쳐진다고 한다. 원래 설계에서는 모든 선반이 올바르게 받쳐져 있고, 모든 선반의 길이는 정수(인치)이다. 로빈슨은 더 정밀하게 잴 도구가 없어서 판자를 오직 정수 인치 단위로만 잘라낼 수 있다. 재설계 후에도 남아 있는 모든 선반은 여전히 올바르게 받쳐져 있어야 한다.

원래 설계를 최대한 적게 바꾸면서 그 오래된 책을 넣을 수 있는 재설계를 찾아라. 먼저, 원래 자리에서 옮겨야 하는 못의 개수를 최소화한다(연산 4와 5는 못 하나를, 연산 6은 못 두 개를 옮긴 것으로 센다). 그런 재설계들 중에서, 잘라내야 하는 판자 길이의 총합을 최소화한다(연산 3과 5는 어느 정도 길이를 잘라내며, 연산 6은 판자 전체를 잘라낸 것으로 센다). 판자의 두께와 못의 지름은 0으로 본다.

책은 회전할 수 없다. 책은 반드시 한 선반 위에 (너비 전체가) 완전히 서 있어야 하며, 다른 선반이나 그 못, 또는 벽감의 가장자리에 닿기만 할 수 있다(겹칠 수는 없다).

첫째 줄에 네 정수 $X_N$, $Y_N$, $X_T$, $Y_T$가 주어진다. 각각 벽감의 너비와 높이, 그리고 오래된 책의 너비와 높이이며 단위는 인치이다($1 \le X_N, Y_N, X_T, Y_T \le 1000$).

둘째 줄에 선반의 개수 $N$이 주어진다($1 \le N \le 100$). 이어지는 $N$개의 줄에는 각각 선반 하나와 그 선반을 받치는 두 못이 다섯 정수 $y_i$, $x_i$, $l_i$, $x1_i$, $x2_i$로 주어진다.

• $y_i$ ($0 < y_i < Y_N$) — 벽감 바닥에서 잰 $i$번째 선반의 높이.
• $x_i$ ($0 \le x_i < X_N$) — 벽감 왼쪽 가장자리에서 $i$번째 선반의 왼쪽 끝까지의 거리.
• $l_i$ ($0 < l_i \le X_N - x_i$) — $i$번째 선반의 길이.
• $x1_i$ ($0 \le x1_i \le l_i/2$) — $i$번째 선반의 왼쪽 끝에서 왼쪽 못까지의 거리.
• $x2_i$ ($l_i/2 \le x2_i \le l_i$; $x1_i < x2_i$) — $i$번째 선반의 왼쪽 끝에서 오른쪽 못까지의 거리.

모든 선반은 서로 다른 높이에 있으며 못으로 올바르게 받쳐져 있다. 입력에는 반드시 해가 존재한다.

공백으로 구분된 두 정수를 출력한다. 첫 번째 정수는 책을 넣기 위해 로빈슨이 원래 자리에서 옮겨야 하는 못의 최소 개수이다. 두 번째 정수는, 그 최소 개수만큼의 못을 옮기는 모든 재설계 중에서, 잘라내야 하는 판자 길이의 최소 총합(인치)이다.