Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P167PROG - ROUND 7G - Ban tự quản

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 ≤ 105) 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 bi và gi (1 ≤ bi, gi ≤ 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. 


Được gửi lên bởi:adm
Ngày:2016-04-10
Thời gian chạy:1s-3s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.