서비스 센터

거대한 2차원 좌표 평면으로 표현할 수 있는 도시가 있다. 이 도시의 원점에는 시청이 있고, 시청에서 부터 동쪽으로 $x$ ㎞ ($x$가 음수인 경우에는 서쪽으로 $-x$ ㎞), 북쪽으로 $y$ ㎞ ($y$가 음수인 경우에는 남쪽으로 $-y$ ㎞) 떨어진 곳의 좌표를 $(x, y)$ 라고 한다. 이 도시의 도로는 모두 남북 방향 혹은 동서 방향이기 때문에, 좌표 $(a, b)$에서 좌표 $(c, d)$까지 가기 위해서는 $(|a-c|+|b-d|)$ ㎞를 가야한다.

이 도시에 넥슨은 $N$ 개의 서비스 센터를 열었으며, 모든 서비스 센터는 $x$축 위에 있다(즉, $y$좌표가 0이다.) $i$ 번째 서비스 센터의 좌표는 $(x_i, 0)$이며, 거리 $L_i$ ㎞ 이하인 위치에 방문 서비스를 진행한다.

이 도시에 있는 $M$ 개의 사무실에서 방문 서비스를 요청했다. $j$ 번째 사무실의 위치는 $(p_j, q_j)$이며, 각 사무실에는 처리해야 할 방문 서비스가 $C_j$ 개 있다. 각 서비스 센터는 거리 조건이 맞는 한 방문 서비스를 처리할 수 있다. 즉, $i$ 번째 서비스 센터가 $j$ 번째 사무실의 방문 서비스를 처리할 수 있으려면, $|x_i - p_j| + |q_j| \le L_i$ 여야 한다.

각 서비스 센터는 하루에 방문 서비스 하나를 처리할 수 있다. 넥슨이 적절한 방법으로 필요한 방문 서비스에 서비스 센터를 할당해서 가장 빠르게 모든 방문 서비스를 처리하려면 최소 며칠이 걸리는지 구하여라.

입력 형식

첫 줄에는 서비스 센터의 수를 나타내는 정수 $N$과 사무실의 수를 나타내는 정수 $M$이 공백으로 구분되어 주어진다. $(1 \le N, M \le 100\,000)$

다음 $N$ 개의 줄의 $i$ 번째 줄에는 서비스 센터의 정보를 나타내는 두 정수 $x_i$와 $L_i$가 공백으로 구분되어 주어진다. $(-1\,000\,000\,000 \le x_i \le 1\,000\,000\,000;$ $0\le L_i \le 1\,000\,000\,000)$

다음 $M$ 개의 줄의 $j$ 번째 줄에는 사무실의 정보를 나타내는 세 정수 $p_j$, $q_j$와 $C_j$가 공백으로 구분되어 주어진다. $(-1\,000\,000\,000 \le p_j, q_j\le 1\,000\,000\,000;$ $1\le C_j \le 1\,000\,000\,000)$

각 방문 서비스를 적어도 하나의 서비스 센터는 처리할 수 있음이 보장된다.

출력 형식

첫 줄에 넥슨이 적절한 방법으로 필요한 방문 서비스에 서비스 센터를 할당해서 가장 빠르게 모든 방문 서비스를 처리하는데 걸리는 최소 일수를 출력하여라.

예제

2 4
1 1
4 2
1 -1 6
3 1 4
4 -2 3
2 0 10

12

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설