문제

진흥이가 있는 바다 위에 크기의 격자가 있습니다. 격자의 위에서부터 번째 행, 왼쪽에서부터 번째 열에 위치한 칸을 라고 정의합시다. 진흥이는 에서 출발해 에 도착하려고 합니다. 진흥이는 오른쪽이나 아래쪽으로 한 번에 한 칸씩만 이동할 수 있습니다.

격자의 일부 칸에는 보물이 묻혀 있습니다. 보물이 있는 칸은 총 개이며, 각 에 대하여 칸 에 개의 보물이 묻혀 있습니다. 진흥이가 보물이 묻혀 있는 칸에 도착하면 그 칸의 보물을 모두 얻을 수 있습니다.

또한 격자에는 개의 위험 구역이 있습니다. 각 위험 구역은 네 개의 정수 로 표현되며, 이는 진흥이가 직사각형 범위 , 에 속하는 칸 를 지나갈 수 없음을 의미합니다. 이때 위험 구역이 진흥이의 시작점 과 도착점 를 포함하지 않음이 보장됩니다.

진흥이는 이 격자에서 최대한 많은 보물을 얻고 부자가 된 다음, 하루 종일 청소년 IT경시대회 문제를 풀며 노는 인생을 살고 싶어합니다. 진흥이가 에 도착할 수 있는지 판단하고, 도착할 수 있다면 진흥이가 가져갈 수 있는 보물의 최대 개수를 구해 주세요.

입력

첫 번째 줄에 네 정수 , , , 이 주어집니다.

다음 개의 줄 각각에는 보물의 정보를 나타내는 세 정수 , , 가 주어집니다. 이는 에 개의 보물이 묻혀 있음을 의미합니다.

다음 개의 줄 각각에는 각 위험 구역을 나타내는 네 정수 , , , 가 주어집니다.

출력

진흥이가 에 도착할 수 있다면 진흥이가 가져갈 수 있는 보물의 최대 개수를 한 줄에 출력합니다.

진흥이가 에 도착할 수 없다면 한 줄에 을 출력합니다.

채점

제한:

• ,
• 각 보물의 위치는 서로 다릅니다.
• 위험 구역이 또는 를 포함하지 않습니다.

서브태스크: