오늘은 고기 파티가 열리는 날이다. 파티에 걸맞도록, 기다란 그릴 위에 잘 구워진 고기가 총 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를 만족하는 모든 고기에 꽂히게 된다.
그 다음, 꼬치를 통째로 들고 자리로 돌아간다. 이때 하나 이상의 꼬치가 꽂힌 고기는 모두 같이 들려 가고 그릴 위에서 사라진다.
둘 중 하나의 꼬치만 꽂힌 고기는 들고 가다 바닥에 떨어진다. 두 꼬치가 모두 꽂힌 고기만 자리로 가져가서 먹을 수 있다.

파티의 주최자인 당신은 각 사람이 어떤 고기를 가져가서 먹게 될지가 궁금하다.

각 사람이 가져가서 먹게 되는 고기의 맛 수치의 합을 구하여 보자.

들고 가다 떨어트린 고기는 합에서 제외해야 함에 유의하라.

고기 파티 timer 3초 memory 1024MB

고기 파티 3초 1024MB