JOI có \(N\) nhân viên, tất cả làm việc trong khoảng thời gian từ 0 đến \(M\) và đều ở trong công ty tại hai thời điểm đó. Hôm nay, nhân viên \(i\) ra ngoài đúng một lần tại \(S_i\) và trở lại tại \(T_i\). Không có hai sự kiện ra hoặc vào nào cùng thời điểm.

Cửa có khóa, ban đầu khóa đóng. Từ bên trong, ai cũng có thể mở hoặc đóng khóa; từ bên ngoài, chỉ người có chìa mới làm được. Khi trở lại, mỗi người phải vào được: họ phải có chìa hoặc khóa đang mở. Khi trở lại, hoặc khi người có chìa rời công ty, họ tùy ý đóng khóa; người không có chìa không thể đóng khóa khi rời đi. Nhân viên chỉ được thao tác khóa đúng lúc chính mình ra hoặc vào, và chìa không được chuyển giữa người.

Giám đốc phát chìa cho đúng \(K\) người. Hãy tối đa hóa tổng thời gian khóa ở trạng thái đóng trong \([0,M]\).

Dữ liệu vào

Dòng đầu chứa \(N,M,K\). Mỗi trong \(N\) dòng sau chứa \(S_i,T_i\).

Dữ liệu ra

In tổng thời gian đóng khóa lớn nhất.

Ràng buộc

Toàn bộ \(2N\) giá trị \(S_i,T_i\) đôi một khác nhau.

Phân nhóm

• Nhóm 1 (10 điểm): \(N\le20\), \(M\le1\,000\,000\).
• Nhóm 2 (90 điểm): không có ràng buộc bổ sung.

Ví dụ

4 20 2
3 11
5 15
6 10
12 18

13

20 100000 8
29930 89724
56133 70462
28063 78568
32483 64351
9410 20176
55809 62944
32450 85190
73536 73966
20452 78868
45458 63484
8286 47425
76018 81622
16736 49308
85383 94641
25100 40002
22158 22821
23508 41781
61709 98882
58110 78431
28448 89247

72454