시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 0 0 0 0.000%

문제

평화로운 어느 도시에 핵폭탄이 투하되어 도시 전체가 폐허가 되었다. 오랜 시간이 흘러 이 도시에 다시 사람들이 모이게 되었는데, 핵폭탄이 떨어진 위치에 아직 핵폐기물이 남아있었다. 평화로운 도시에 살던 사람들은 핵폐기물의 위험에 대해 잘 몰랐기 때문에, 단순히 이를 둘러싸는 벽을 만들기로 하였다.

핵폭탄의 주변에는 원래 N(3≤N≤100)개의 벽이 있었는데, 핵폭탄으로 인해 각 벽들이 무너지게 되었다. 도시에서는 이러한 벽들을 수리하기로 하였는데, 각 지역의 높이 차이와 파괴된 정도, 그리고 벽의 재질 등으로 각각의 벽들을 수리하는데 필요한 비용이 다를 수도 있다. 도시에서는 이러한 벽들 중 일부(혹은 전부)를 이용하여 최소의 비용으로 벽을 만들기로 하였다.

핵폐기물을 둘러싸는 벽을 만들 때에는, 그 벽들이 완전히 연결되는 볼록 다각형의 형태가 되어야 한다. 각각의 벽들을 하나의 선분이라고 생각했을 때, 그 선분 위에 핵폐기물이 위치하는 경우는 없다고 가정한다. 하지만 도시에서 이전에 있던 벽들에 대한 정보를 판단할 때 착오가 있을 수도 있기 때문에, 서로 다른 두 벽들이 이루는 선분이 서로 교차하는 경우는 있을 수도 있다.

핵폐기물의 위치와 벽들에 대한 정보가 주어졌을 때, 핵폐기물을 둘러싸는 볼록 다각형 형태의 벽을 만들이 위해 필요한 최소 비용을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 N, X, Y가 주어진다. (X, Y)는 핵폐기물의 위치를 나타낸다. 다음 N개의 줄에는 각각의 벽에 대한 정보를 나타내는 세 정수 x1, y1, x2, y2, C(1≤C≤10,000)가 주어진다. 이는 두 점 (x1, y1), (x2, y2)를 연결하는 벽을 재건하기 위해 필요한 비용이 C임을 의미한다. 모든 좌표들은 절대값이 10,000을 넘지 않는 정수이다.

출력

첫째 줄에 답을 출력한다. 불가능한 경우에는 -1을 출력한다.

예제 입력

3 0 0
1 1 2 2 10000
3 3 4 4 10000
5 5 6 6 10000

예제 출력

-1

힌트