VOI 14 Bài 1 - Con đường Tùng Trúc

Xem dạng PDF

Gửi bài giải


Điểm: 0,30 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
VOI 2014
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Địa điểm du lịch Dailai nổi tiếng với con đường Tùng-Trúc. Đó là một con đường dài và thẳng, dọc bên đường người ta trồng rất nhiều cây tùng và cây trúc. Với mục đích tạo điểm nhấn cho con đường, Ban quản lý khu du lịch muốn chọn một đoạn đường mà dọc theo nó có ít nhất ~a~ cây tùng và có ít nhất ~b~ cây trúc để trang trí. Sau khi khảo sát, Ban quản lý ghi nhận được vị trí của từng cây tùng và cây trúc. Trên con đường có tất cả ~n~ cây, không có hai cây nào ở cùng một vị trí. Cây thứ ~i~ ở vị trí có khoảng cách đến vị trí bắt đầu của con đường là ~d_i~ (~i = 1, 2, \dots, n~). Với kinh phí có hạn, Ban quản lý muốn chọn một đoạn đường thỏa mãn điều kiện đã nêu với độ dài là ngắn nhất.

Cho ~a~, ~b~ và vị trí của ~n~ cây. Hãy tìm đoạn đường có độ dài ngắn nhất mà dọc theo đoạn đường đó có ít nhất ~a~ cây tùng và ~b~ cây trúc.

Input

  • Dòng đầu chứa 3 số nguyên dương ~n~, ~a~, ~b~ (~a + b \le n~)
  • Dòng thứ ~i~ trong ~n~ dòng tiếp theo mỗi dòng chứa hai số nguyên dương ~d_i~ (~d_i \le 10^9~) trong đó ~d_i~ là khoảng cách của cây tính từ vị trí bắt đầu của con đường, ~k_i = 1~ nếu cây thứ ~i~ là cây tùng, ~k_i = 2~ nếu là cây trúc.
  • Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Output

Ghi ra một số nguyên là độ dài đoạn đường ngắn nhất tìm được, quy ước ghi số ~-1~ nếu không tồn tại đoạn đường nào thỏa mãn điều kiện đặt ra.

Giới hạn

  • 30% số test có ~n \le 300~.
  • 30% số test khác có ~n \le 3000~.
  • 40% số test còn lại có ~n \le 300000~.

Sample Input

7 2 2
20 2
30 1
25 1
35 1
60 2
65 2
10 1

Sample Output

35

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • -18
    tronghuy  đã bình luận lúc 14, Tháng 9, 2022, 22:54

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -45
    minhpro2k8  đã bình luận lúc 16, Tháng 12, 2021, 10:38

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • 0
      hung3a8  đã bình luận lúc 16, Tháng 12, 2021, 10:51

      Các comment của bạn hiện đang vi phạm điều 2 trong nội quy comment:

      Không comment nhảm. Comment không liên quan đến bài viết có thể dẫn đến việc bị xóa comment và cấm comment.
      

      Bạn sẽ bị cảnh cáo lần 1. Trong trường hợp tái diễn, tài khoản của bạn sẽ bị cấm bình luận.

      Xin cảm ơn.


  • -39
    minhpro2k8  đã bình luận lúc 16, Tháng 12, 2021, 10:38

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -41
    Nonamekontum  đã bình luận lúc 2, Tháng 12, 2021, 8:31

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -56
    phong23306mm  đã bình luận lúc 2, Tháng 10, 2021, 16:11 chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.