#375. CAKEBOILED - Luộc bánh Chưng

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: Chưa có dữ liệu
Đưa lên bởi: Chùm CUỐI

Đề bài

Như thường lệ, cứ vào dịp tết Nguyên Đán, nhà trường lại tổ chức cho các lớp gói bánh Chưng đón tết. Sau công đoạn gói là tới công đoạn luộc. Do có nhiều lớp tham gia gói nên nhà trường phải có kế hoạch chia khu vực cho các lớp luộc bánh. Để đảm bảo mỹ quan và có không khí tết, nhà trường chuẩn bị một dải đất có chiều dài L để chia cho các lớp làm địa điểm luộc. Dải đất được chia ra thành L ô đánh số từ 1 đến L . Có n lớp tham gia gói và luộc bánh. Nhà trường dự kiến chia cho lớp thứ i các ô từ a_i đến b_i (1 ≤ i ≤ n) . Các lớp sẽ nhận địa điểm luộc bánh theo thứ tự từ 1 đến n . Tuy nhiên các đoạn được dự kiến chia cho các lớp có thể có những ô trùng nhau nên nếu đến lượt lớp nào nhận mà có ô đã bị lớp trước đó nhận rồi thì sẽ không được nhận ô đó nữa.

Yêu cầu: Hãy tính số ô nhiều nhất mà một lớp có thể nhận được theo dự kiến và số ô nhiều nhất mà một lớp nhận được trên thực tế.

Dữ liệu vào:

  • Dòng đầu chứa hai số nguyên dương n L ;
  • n dòng tiếp theo, dòng thứ i chứa hai số nguyên dương a_i, b_i .

Hai số liên tiếp trên một dòng được ghi cách nhau một dấu cách.

Dữ liệu ra:

Ghi trên một dòng hai số nguyên theo thứ tự là số ô nhiều nhất mà một lớp nhận được theo dự kiến và số ô nhiều nhất mà một lớp nhận được trên thực tế. Hai số liên tiếp được ghi cách nhau một dấu cách.

Ví dụ:

Dữ liệu vào:
3 10
2 4
7 8
6 9
Dữ liệu ra:
4 3
Giải thích:

(Lớp số 1 nhận được 3 ô màu xanh, lớp số 2 nhận được 2 ô màu vàng, lớp số 3 nhận được 2 ô màu đỏ do hai ô màu vàng đã bị lớp số 2 nhận trước rồi).

  • Theo dự kiến thì lớp số 3 nhận được nhiều ô nhất là 4 ô.
  • Thực tế thì lớp số 1 nhận được nhiều nhất là 3 ô (hình trên).

Giới hạn:

  • Trong tất cả các test: 1 ≤ n, L ≤ 1000; 1 ≤ a_i ≤ b_i ≤ L .