Hôm nay, trong giờ học thủ công, Mofk được học cách gấp máy bay phản lực bằng giấy nhưng loay hoay mãi không gấp được nên Mofk cũng đành bó tay. Trong lúc chờ sự trợ giúp từ thầy giáo, vì chán quá nên Mofk đã đặt chồng các tờ giấy có kích thước khác nhau. Chợt có một bài toán hay nảy ra trong đầu khiến Mofk vô cùng thích thú:
Cho ~n~ tờ giấy hình chữ nhật, tờ giấy thứ ~i~ có góc trái dưới ở ~(0, 0)~ và góc phải trên ở ~(x_i, y_i)~. Hãy tìm diện tích phần bị phủ bởi đúng ~k~ tờ giấy.
Thầy giáo đã đến để giúp Mofk gấp máy bay, trong thời gian đó bạn hãy thử giải bài toán Mofk vừa nghĩ ra nhé!
Input
Dòng đầu gồm ~2~ số nguyên dương ~n~ và ~k~ ~(1 \le k \le n \le 10^6)~.
Trong ~n~ dòng tiếp theo, dòng thứ ~i~ gồm 2 số nguyên dương ~x_i~, ~y_i~ ~(1 \le x_i, y_i \le 10^6)~, là tọa độ góc phải trên của tờ giấy thứ ~i~.
Output
Gồm một số nguyên dương duy nhất là diện tích phần bị phủ bởi đúng ~k~ tờ giấy hình chữ nhật
Scoring
~20\%~ số test có ~x_i \le x_{i+1}, y_i \le y_{i+1}~ ~\forall~ ~1 \le i \le n - 1~.
~30\%~ số test khác có ~n \le 1000~.
~50\%~ số test còn lại không có ràng buộc gì thêm.
Sample Input 1
5 2
1 4
2 3
3 5
2 7
4 1
Sample Output 1
4
Notes
*Giải thích test ví du: *
Một phần có diện tích là ~3~ được phủ bởi đúng 2 tờ giấy có tọa độ phải trên là ~(2;7), (3;5)~.
Một phần có diện tích là ~1~ được phủ bởi đúng 2 tờ giấy có tọa độ phải trên là ~(3;5), (4;1)~
Bình luận