아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Cow-libi

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

요약
시간이 주어진 여러 목초지 방문 기록에 대해, 모든 방문 지점에서 제때 도달할 수 없는 알리바이의 개수를 센다.
난이도

보통10점 중 6점

유형
수학, 기하, 누적 합
정답자
아직 제출이 없습니다

문제

Somebody has been grazing in Farmer John's (1≤G≤105)(1 \le G \le 10^5) private gardens! Using his expert forensic knowledge, FJ has been able to determine the precise time each garden was grazed. He has also determined that there was a single cow that was responsible for every grazing incident.

In response to these crimes each of FJ's NN (1≤N≤105)(1 \le N \le 10^5) cows have provided an alibi that proves the cow was in a specific location at a specific time. Help FJ test whether each of these alibis demonstrates the cow's innocence.

A cow can be determined to be innocent if it is impossible for her to have travelled between all of the grazings and her alibi. Cows travel at a rate of 1 unit distance per unit time.

입력

The first line of input will contain GG and NN separated by a space.

The next GG lines contain the integers xx, yy, and tt (−109≤x,y≤109;0≤t≤109)(-10^9 \le x, y \le 10^9; 0 \le t \le 10^9) separated by a space describing the location and time of the grazing. It will always be possible for a single cow to travel between all grazings.

The next NN lines contain xx, yy, and tt (−109≤x,y≤109;0≤t≤109)(-10^9 \le x, y \le 10^9; 0 \le t \le 10^9) separated by a space describing the location and time of each cow's alibi.

출력

Output a single integer: the number of cows with alibis that prove their innocence.

예제1

  1. 예제 1

    입력
    2 4
    0 0 100
    50 0 200
    0 50 50
    1000 1000 0
    50 0 200
    10 0 170
    
    예상 출력
    2