Nam là một tài xế xe buýt đi từ trạm 1 đến trạm thứ ~p~. Thời gian để di chuyển giữa hai trạm liên tiếp là 1 phút (xuất phát từ trạm 1 tại thời điểm ~t~ thì xe đến trạm ~i~ tại thời điểm ~t + i - 1~). Cho biết thời gian và địa điểm chờ của ~n~ hành khách đón xe buýt, hãy giúp Nam xác định thời gian xuất phát từ trạm thứ 1 sớm nhất để có thể đón ít nhất ~m~ hành khách. Biết rằng xe buýt có sức chứa không giới hạn.

Dữ liệu

• Dòng thứ nhất ghi ba số nguyên dương ~n, m, p~ ~(1 \le n, p \le 10^5,\ 1 \le m \le n)~ — số hành khách chờ xe buýt, số hành khách ít nhất Nam phải đón và số trạm xe buýt.

• ~n~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên dương ~a_i~ và ~b_i~ ~(1 \le a_i \le p,\ b_i \le 10^9)~ — hành khách thứ ~i~ bắt đầu chờ tại trạm ~a_i~ từ thời điểm ~b_i~.

Kết quả

In ra thời điểm xuất phát từ trạm 1 sớm nhất để Nam có thể đón ít nhất ~m~ hành khách.

Ví dụ

Sample Input

7 4 5
1 1
2 4
4 10
5 8
3 5
5 6
4 7

Sample Output

3

Giải thích

• Nếu Nam xuất phát tại thời điểm 3 thì sẽ đón được hành khách thứ 1, 2, 5 và 6.