생명을 구할까, 돈을 구할까

마을 "Under The Sea"는 계곡 안에 있다. 마을의 유일한 입구 앞에는 큰 강이 흐른다. 올해는 약 100년에 한 번 찾아오는 홍수가 닥쳤다. 정부의 대응이 늦어 주민을 대피시킬 시간이 없다. 곧 물이 마을로 밀려든다.

다행히 마을에는 물을 막을 수 있는 벽과 문이 있다. 하지만 바깥의 물을 모두 막을 수는 없다. 그렇게 하면 강을 따라 너무 많은 물이 흘러 근처의 원자력 발전소가 파괴되고, 모든 사람에게 헤아릴 수 없는 피해가 생긴다. 따라서 감당할 수 있는 방식으로 물을 일부 들여보내야 한다.

벽과 문은 마을을 여러 개의 닫힌 구역으로 나눈다. 모든 문을 열면 서로 다른 두 구역은 문을 지나는 경로가 정확히 하나씩 존재한다. 예를 들어 예제 1은 구역 1개, 벽 2개, 문 1개로 이루어진 마을이다. 그림에서 실선은 벽이고 점선은 문이다. 예제 2는 구역 5개, 벽 5개, 문 5개로 이루어진 마을이다.

정부는 닫을 문과 열어 둘 문을 정할 수 있다. 홍수는 일부 구역을 파괴하고 나머지 구역은 안전하게 남긴다. 그림에서 색칠된 구역은 예제 출력의 최적 계획에서 파괴되는 구역이다.

한 공무원이 어느 문을 열지 고르는 프로그램을 작성해 달라고 요청했다. 주민 전체의 위치와 소유한 돈이 주어진다. 공무원은 총 재산을 가장 많이 지키는 계획을 원한다. 그러나 부자와 가난한 사람을 다르게 대하는 것은 옳지 않다고 느껴, 몰래 다른 계획을 세우려 한다. 구하는 사람 수가 가장 많은 계획을 제시하는 것이다. 구하는 사람 수가 같은 계획이 여러 개라면 그중 구하는 돈이 가장 많은 계획을 고른다.

첫 줄에는 정수 Area가 주어진다. 홍수가 파괴할 것으로 예상되는 면적이다.

둘째 줄에는 세 정수 G, W, R이 주어진다. 각각 문의 개수, 벽의 개수, 주민의 수이다.

이어서 G개의 줄에 문 하나의 양 끝점 좌표 x1g, y1g, x2g, y2g가 주어진다.

이어서 W개의 줄에 벽 하나의 양 끝점 좌표 x1w, y1w, x2w, y2w가 주어진다.

마지막으로 R개의 줄에 주민의 좌표 xr, yr과 소유한 돈 moneyr이 주어진다.

두 줄을 출력한다. 첫 줄에는 실수 하나와 정수 세 개를 출력한다. 실수는 area이며 파괴된 구역의 총 면적을 소수점 첫째 자리까지 반올림한 값이다. 이어지는 정수는 money, people, gate_n으로, 각각 피해자의 총 금액, 피해자 수, 열린 문의 수이다.

둘째 줄에는 열린 문의 번호 gate_n개를 순서에 상관없이 출력한다. 문은 1부터 G까지 번호가 매겨져 있다.

입력의 Area가 마을 면적보다 크면, 출력하는 면적은 마을 전체 면적이고, money는 모든 주민이 가진 돈의 합, people은 전체 주민 수이다. 이때 모든 문을 열어야 한다.

Area가 마을 면적 이하이면, 출력하는 면적은 Area 이상이어야 한다. 구하는 사람 수가 같은 계획이 여럿이면 잃는 돈이 적은 계획을 고른다. 그래도 같으면 파괴되는 면적이 작은 계획을 고른다. 그래도 같으면 아무거나 된다.

• $0 < Area, G, W, R < 5000$
• $-5000 < x, y < 5000$
• $0 \le money < 5000$
• 마을의 경계에는 문이 정확히 하나 있다. 물은 이 문을 통해 마을로 들어온다. 실행 가능한 계획이라면 이 문은 반드시 열어야 한다.
• 모든 구역은 단순 다각형이다. 자기 자신과 교차하지 않으며 구멍이 없다.
• 벽과 문은 서로 교차하지 않는다. 끝점에서만 맞닿는다.
• 모든 끝점에는 벽이나 문이 최소 두 개 연결된다. 매달린 벽이나 문은 없다.
• 모든 주민은 구역의 내부에 있다. 마을 밖에 있지 않으며, 벽, 문, 분기점 위에 놓이지 않는다.