Phòng máy tính


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

Nhà trường THPT nọ muốn tổ chức ngày chạy thử phần mềm thi trực tuyến. Vì vậy, trường cần $N$ học sinh đến kiểm thử. Biết rằng, học sinh thứ $i$ sẽ đến trường và sử dụng thử từ lúc $a_i$ đến hết $b_i$ đơn vị thời gian (đvtg).

Sẽ có những lúc có nhiều học sinh cùng chạy thử trong một đơn vị thời gian. Vì vậy, sẽ có những lúc phòng máy tính quá tải. Nhà trường hiện đang có $M$ máy tính. Hãy cho biết, nhà trường cần thuê thêm ít nhất bao nhiêu máy tính để có đủ máy tính cho ngày kiểm thử.

Dữ liệu

  • Dòng đầu tiên chứa hai số nguyên $N, M \ (1\le N, M\le 10^5)$;
  • $N$ dòng tiếp theo, mỗi dòng ghi hai số nguyên $a_i, b_i \ (1\le a_i \le b_i \le 10^5)$.

Kết quả

  • Kết quả bài toán.

Chấm điểm

60; $N\le 10^3; b_i \le 10^3$. 40; Không có giới hạn gì thêm.

Ví dụ

Ví dụ 1

input

6 3
1 4
2 5
3 4
1 3
2 2
3 4

output

2

Giải thích

  • Trong giờ đầu tiên, có 2 học sinh sử dụng máy tính.
  • Trong giờ thứ hai và thứ tư, có 4 học sinh sử dụng máy tính.
  • Trong giờ cuối cùng, có 1 học sinh sử dụng máy tính.
  • Trong giờ thứ ba, có 5 học sinh sử dụng máy tính.
  • Do trong giờ thứ ba có 5 học sinh sử dụng đồng thời, vì vậy nhà trường cần thuê thêm 2 máy tính nữa.

Comments

There are no comments at the moment.