오늘은 고기 파티가 열리는 날이다. 파티에 걸맞도록, 기다란 그릴 위에 잘 구워진 고기가 총 \(N\)개 놓여 있다.

그릴을 \(10^9\) 의 길이를 가진 선분이라고 하고, 그릴의 왼쪽 끝을 좌표 0, 오른쪽 끝을 좌표 \(10^9\) 이라고 하자. 각 고기는 그릴 위에서 특정 구간을 차지하고 있으며, 양의 정수로 표현되는 맛 수치를 각각 가진다. \(i\)번째 고기는 \((1 \le i \le N)\) 구간 \([s_i , e_i ]\)에 해당하는 좌표를 차지하고 있으며 맛 수치는 \(t_i\)이다. 여러 고기가 겹쳐 있을 수 있다.

파티에는 \(M\) 명의 사람이 참석하였다. 1 번 사람부터 \(M\) 번 사람까지 번호 순서대로 그릴 앞에 서서 각자 먹을 고기를 가져간다. 고기를 가져가는 방법은 다음과 같다.

• \(j\) 번 사람은 (\(1 \le j \le M)\) 긴 꼬치 두 개를 가지고 와서 각각 \(a_j + 0.1, b_j + 0.9\) 좌표에 찔러 넣는다. \((a_j \le b_j )\) 좌표 \(x\)에 찔러 넣은 꼬치는 \(s_i \le x \le e_i\)를 만족하는 모든 고기에 꽂히게 된다.
• 그다음, 꼬치를 통째로 들고 자리로 돌아간다. 이때 하나 이상의 꼬치가 꽂힌 고기는 모두 같이 들려 가고, 그릴 위에서 사라진다.
• 둘 중 하나의 꼬치만 꽂힌 고기는 들고 가다 바닥에 떨어진다. 두 꼬치가 모두 꽂힌 고기만 자리로 가져가서 먹을 수 있다. 

파티의 주최자인 당신은 각 사람이 어떤 고기를 가져가서 먹게 될지가 궁금하다. 각 사람이 가져가서 먹게 되는 고기의 맛 수치의 합을 구하여 보자. 들고 가다 떨어트린 고기는 합에서 제외해야 함에 유의하라.

첫 번째 줄에 고기의 수 \(N\)과 사람의 수 \(M\)이 주어진다.

다음 줄부터 \(N\)개의 줄에 걸쳐, 이 중 \(i\)번째 줄에는 \(i\)번째 고기가 차지하는 구간과 맛 수치를 나타내는 세 정수 \(s_i , e_i , t_i\)가 주어진다. 

다음 줄부터 \(M\)개의 줄에 걸쳐, 이 중 \(j\)번째 줄에는 \(j\) 번 사람이 꼬치를 어느 좌표에 찔러 넣을지를 나타내는 두 정수 \(a_j , b_j\)가 주어진다

제약 조건

• 주어지는 모든 수는 정수이다.
• \(1 \le N, M \le 250 000\)
• \(0 \le s_i < e_i \le 10^9 (1 \le i \le N)\)
• \(1 \le t_i \le 10^9 (1 \le i \le N)\)
• \(0 \le a_j \le b_j \le 10^9 − 1 (1 \le j \le M)\)

부분문제

1. (5점) \(N, M \le 1, 000\)
2. (9점) \(e_i − s_i \le 5 (1 \le i \le N)\)
3. (11점) \(s_i < s_{i+1}, e_i > e_{i+1} (1 \le i \le N − 1)\)
4. (23점) \(e_i − s_i = e_1 − s_1 (2 \le i \le N)\)
5. (52점) 추가 제약 조건이 없음.