Panorama

Shoot! Take a Panorama 깊은 어둠 속 빛나는 별처럼 우린 어디서든 서로 알아볼 수 있어

IZ*ONE의 멤버 12명은 <One-reeler / Act IV> 앨범 커버의 순서대로 안유진, 김채원, 강혜원, 조유리, 혼다 히토미, 김민주, 장원영, 미야와키 사쿠라, 권은비, 야부키 나코, 최예나, 이채연이다. IZ*ONE 멤버들은 그룹이 해체되기 전 매우 많은 칸으로 이루어진 긴 복도에서 $N$장의 파노라마 사진을 찍었다. $i$번째 파노라마 사진은 $s_i$번째 칸부터 $e_i$번째 칸까지의 이미지를 담고 있다. 사진의 길이는 한 칸당 $M$이다.

몇 년 뒤 다시 만난 IZ*ONE 멤버들은 $N$개의 파노라마를 합쳐서 보관하려고 한다. 먼저 각 파노라마 사진을 칸마다 자른다. 다음으로, 어떤 칸을 찍은 부분 사진이 하나뿐이라면 보존하고, 둘 이상이라면 그 칸을 찍은 부분 사진을 모두 버린다. 마지막으로 남아 있는 부분 사진을 칸 번호의 순서대로 모두 이어 붙이되, 인접하지 않은 칸을 찍은 두 부분 사진 사이에는 길이 $1$의 검은 종이 한 장을 끼워 넣는다. 아래 그림의 상황은 예제 입력과 다름에 유의하라.

IZ*ONE 멤버들은 이어 붙인 사진을 하나의 상자에 넣으려고 한다. 그러나 사진의 총 길이를 알지 못해, 알맞은 크기의 상자를 구하는 데 어려움을 겪고 있다. 멤버들을 도와 사진의 총 길이를 구해 보자!

첫 번째 줄에 두 양의 정수 $N$, $M$이 공백으로 구분되어 주어진다.

두 번째 줄부터 $N$개의 줄에는 각 파노라마 사진의 시작 칸과 끝 칸을 나타내는 두 정수 $s_i$, $e_i$가 공백으로 구분되어 주어진다.

첫 번째 줄에 완성된 사진의 총 길이를 출력한다.

• $1 \le N \le 10^5,1 \le M \le 10^9$
• $1 \le s_i \le e_i \le 10^9$

문제 스토리의 아이디어는 운영진에 있는 WIZ*ONE이 제공하였다.