큰 침대

시간 제한1초메모리 제한1024 MB

요약

포털 1번에서 n번까지 통과할 수 있는 정수 크기의 직육면체 중 부피가 가장 큰 것을 구합니다.

난이도: 보통10점 중 7점
유형: 그래프, BFS, 완전 탐색
정답자: 아직 제출이 없습니다

문제

먼 은하의 어딘가, 니비루 행성에서 가장 촉망받는 학생 중 한 명인 바실리우스가 명문 니비루 국립대학교(NSU)의 특별 장학금을 받았다. 그는 기숙사 방에 놓을 침대를 사기로 했다.

그는 부피가 최대한 큰 침대를 원하지만, 앞으로 살 침대의 크기는 제한되어 있다. 바실리우스는 방에 앞으로 쇼핑에서 얻을 전리품을 둘 공간도 남겨 두고 싶어 한다.

가게에서는 직육면체이기만 하면 어떤 침대든 만들 수 있다. 하지만 가게에서 기숙사 방까지 모든 침대를 배달할 수 있는 것은 아니다. 침대는 일반 직사각형 문과 비슷한 포털을 통과해서 옮겨야 한다. 포털은 바닥에 수직이다. 포털을 지나면 다른 포털 근처나 방 중 한 곳으로 이동한다. 바실리우스가 방에 맞는 침대의 최적 크기를 계산하도록 도와라. 포털 사이의 거리는 기숙사 방의 크기보다 훨씬 크다.

침대는 한 면이 항상 바닥과 평행하고, 다른 한 면이 현재 지나고 있는 포털이 놓인 평면과 평행하도록 놓인다.

침대는 포털을 통과해 방으로 옮기려고 들어 올린 뒤에는 회전하지 않는다.

입력

첫 줄에는 침대의 크기를 제한하는 정수 $a$ , $b$ , $c$ 가 주어진다. 침대의 세 변(길이, 너비, 높이) 중 하나는 $a$ 를 넘지 않고, 다른 하나는 $b$ 를 넘지 않으며, 나머지 하나는 $c$ 를 넘지 않는다( $1 \le a, b, c \le 500$ ).

다음 줄에는 행성에 있는 포털의 개수 $n$ 이 주어진다( $2 \le n \le 500$ ). 포털은 1번부터 $n$ 번까지 번호가 매겨져 있다. 가게의 포털은 1번이고, 바실리우스의 방으로 이어지는 포털은 $n$ 번이다.

이어지는 $n$ 개의 줄은 포털을 한 줄에 하나씩 설명한다. $i$ 번째 줄은 실수 $w_i$ , $h_i$ , $k_i$ 로 시작한다. $w_i$ 와 $h_i$ 는 포털의 너비와 높이이고, $k_i$ 는 그 포털을 지나 바로 갈 수 있는 포털의 개수다( $1 \le w_i, h_i \le 300$ , $0 \le k_i < n$ ). 이어서 서로 다른 정수 $k_i$ 개 $p_{ij}$ 가 주어지는데, 이는 $i$ 번 포털에서 바로 갈 수 있는 포털의 번호다( $1 \le p_{ij} \le n$ , $p_{ij} \ne i$ ).

출력

세 개의 양의 정수 $x$ , $y$ , $z$ 를 순서와 상관없이 출력한다. 이 값들은 바실리우스가 가게에서 기숙사 방으로 가져올 수 있는, 부피가 가장 큰 침대의 크기다. 최대 부피를 갖는 경우가 여러 개라면 그중 아무거나 출력해도 된다. 해가 존재함이 보장된다.

예제2

예제 1

입력

300 300 300
4
300 300 1 2
100 200 1 4
300 200 1 1
300 300 2 3 1

예상 출력

100 200 300

예제 2

입력

300 300 300
4
300 300 2 2 3
100 200 1 4
300 200 1 4
300 300 1 1

예상 출력

200 300 300