Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Nhằm đổi mới quản lý, trường tiểu học KĐ tiến hành bầu chọn Ban tự quản. Theo qui định, việc bầu chọn được tiến hành theo qui trình sau: Ban bầu cử lập danh sách tất cả các lớp trong trường và phân ra thành các nhóm. Mỗi nhóm sẽ gồm 1 hoặc một số lớp liên tiếp nhau trong danh sách. Kết quả của việc phân nhóm là mỗi lớp sẽ thuộc vào đúng một nhóm. 

      Mỗi nhóm sẽ đề cử 2 ứng viên tham gia vào Ban tự quản của trường: một ứng viên là học sinh nam và một ứng viên là học sinh nữ. Tiếp đến, mỗi học sinh sẽ bỏ phiếu chọn một trong hai ứng viên thuộc nhóm của mình. Biết rằng các học sinh nam chỉ bầu cho ứng viên nam và các học sinh nữ chỉ bầu cho ứng viên nữ. Kết quả kiểm phiếu sẽ được thống kê theo từng nhóm. Ứng viên nhận được nhiều phiếu bầu chọn nhất trong nhóm của mình sẽ trúng cử vào Ban tự quản. Trong trường hợp hai ứng viên có cùng số phiếu, cả hai ứng viên đều trúng cử vào Ban tự quản. 

      Giả sử kết quả bầu cử có B học sinh nam và G học sinh nữ được bầu vào Ban tự quản. Theo kinh nghiệm tích luỹ từ những năm trước, Ban bầu cử thấy rằng hiệu số B–G càng lớn thì Ban tự quản làm việc càng hiệu quả. Lưu ý rằng hiệu số này có thể là số âm. Ban bầu cử muốn cực đại hiệu số này chứ không phải trị tuyệt đối của nó. Ví dụ: nếu B = 2, G = 5 thì B – G = –3, còn nếu B = 3, G = 4 thì hiệu số này là B – G = –1, kết quả thứ hai được tính là tốt hơn.

      Trường KĐ có n lớp và Ban bầu cử đã lập danh sách các lớp được đánh số theo thứ tự từ 1 đến n. Bây giờ, Ban bầu cử cần tìm cách phân nhóm, mỗi nhóm gồm ít nhất l lớp (để số thành viên trong Ban tự quản là không quá lớn) và không quá r lớp (để các học sinh dễ có sự đồng thuận khi bầu cử). Chú ý là các lớp trong mỗi nhóm phải có số thứ tự liên tiếp trong danh sách lớp đã lập, mỗi lớp thuộc đúng một nhóm.

Yêu cầu: Hãy giúp Ban bầu cử tìm cách phân nhóm để kết quả bầu cử cho ban tự quản hoạt động hiệu quả nhất (cho giá trị cực đại của hiệu B–G).

Input

• Dòng đầu tiên chứa ba số nguyên n, l, r (1 ≤ l ≤ r ≤ n ≤ 10⁵) theo thứ tự là số lượng lớp học trong trường, cận dưới và cận trên cho số lớp trong một nhóm;
• Dòng thứ i trong số n dòng tiếp theo chứa hai số nguyên b_i và g_i (1 ≤ b_i, g_i ≤ 10000) là số lượng học sinh nam và số lượng học sinh nữ trong lớp thứ i (i = 1, 2, …, n).

Hai số liên tiếp trên cùng dòng được ghi cách nhau bởi dấu cách.

Output

Một số nguyên là hiệu số B–G trong cách phân nhóm tốt nhất tìm được.

Example

Input:

5 1 2

7 5

10 1

2 3

2 6

4 3

Output:

2

Giải thích ví dụ: Một cách phân nhóm tối ưu là:

       Nhóm 1: Lớp số 1; Nhóm 2: Lớp số 2 và lớp số 3; Nhóm 3: Lớp số 4; Nhóm 4: Lớp số 5.

Theo cách phân nhóm này trúng cử vào Ban tự quản là 1 học sinh nam từ nhóm 1, 1 học sinh nam từ nhóm 2, 1 học sinh nữ từ nhóm 3 và 1 học sinh nam từ nhóm 4. Như vậy, Ban tự quản có số lượng học sinh nam là B=3 và số lượng học sinh nữ là G=1.