Năm \(2018\), Khoa Điện - Điện Tử của Trường Đại học Giao thông Vận tải kỉ niệm \(20\) năm thành lập. Các bạn sinh viên đã nghiên cứu làm ra Robot có khả năng lăn sơn tường. Robot được cho thử nghiệm quét vôi bức tường chạy dài \(m\) mét được đánh số từ vị trí \(0\) cho đến vị trí \(m\). Robot được chạy thử nghiệm \(n\) lần, lần thứ \(i\) Robot sẽ quét vôi từ vị trí \(a_i\) đến vị trí \(b_i\) có độ dài là \(b_i - a_i\).

Sau các lần thử nghiệm ở những chỗ nào được lăn sơn ít nhất k lần thì chỗ đó coi như đã sơn xong, các bạn sinh viên muốn biết là bức tường đã sơn xong bao nhiêu mét, biết rằng các lần lăn sơn có thể phủ lên nhau.

Input

Dòng đầu gồm ba số nguyên dương n, m và k tương ứng với số lần quét và độ dài bức tường và số lần sơn ít nhất thì coi như đã sơn xong \(1 \le n \le 10^6, 1 \le m \le 10^6, 1 \le k \le n\).

\(n\) dòng tiếp theo mỗi dòng gồm hai giá trị \(ai, bi\) \((0 \le ai < bi \le m)\).

Output

Một số nguyên duy nhất là số mét mà đã được sơn ít nhất \(k\) lần.

Ví dụ 1

Input

3 100 2
55 72
12 44
30 81

Output

31

Giải thích : Tường đã sơn ít nhất hai lần 30->44 và 55->72 tổng cộng là \((44-30)+(72-55) = 31\) mét

Ví dụ 2

Input

3 100 1    
30 40
50 60
10 20

Output

30

Chú ý:

Thuật toán rất chặt về thời gian, bạn hãy sử dụng scanf và printf thay vì cin và cout