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.|

LQDBUS - Đến trường

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/lqdbus


Trường THPT chuyên Lê Quý Đôn, TP Đà Nẵng có một hệ thống xe buýt riêng. Hằng ngày xe buýt sẽ chạy dọc theo bờ sông Hàn thơ mộng để đón các học sinh đến trường. Trên hành trình, xe buýt sẽ tiếp nhận các học sinh đứng chờ ở các điển hẹn nếu như xe còn chỗ trống. Xe buýt có thể đỗ lại để chờ những học sinh chưa kịp đến điểm hẹn. Tuy nhiên vì học sinh trường Lê Quý Đôn là những học sinh rất coi trọng việc giờ giấc nên họ có thể để xe buýt chờ chứ không bao giờ chịu chờ xe buýt. Điều đó có nghĩa là nếu họ đến điểm hẹn mà xe chưa đến thì họ sẽ tự đi bộ đến trường.

Cho biết thời điểm mà mỗi học sinh đến điểm hẹn của mình và thời điểm qua mỗi điểm hẹn của xe buýt. Giả thiết rằng xe buýt đến điểm hẹn đầu tiên tại thời điểm 0 và thời gian xếp khách lên xe được bằng 0.

Xe buýt cần phải chở một số lượng nhiều nhất các học sinh có thể được đến trường. Hãy xác định khoảng thời gian ngắn nhất để xe buýt thực hiện công việc.

Dữ liệu vào

  • Dòng đầu tiên chứa 2 số nguyên dương n, m theo thứ tự là số điểm hẹn và số chỗ ngồi của xe buýt.
  • Dòng thứ i trong số n dòng tiếp theo chứa số nguyên ti là thời gian cần thiết để xe buýt di chuyển từ điểm hẹn thứ i đến điểm hẹn thứ i+1 (điểm hẹn thứ n+1 sẽ là trường Lê Quý Đôn) và số nguyên k là số lượng học sinh đến điểm hẹn i, tiếp theo k số nguyên là các thời điểm đến điểm hẹn của k học sinh.

Kết qủa

Gồm một dòng duy nhất, là thời gian ngắn nhất tìm được.

Giới hạn

  • 1 ≤ n ≤ 200000, 1 ≤ m ≤ 20000
  • Tổng số học sinh không vượt quá 200000.
  • Kết quả không vượt quá 231-1.

Ví dụ

Dữ liệu:
3 5
1 2 0 1
1 1 2
1 4 0 2 3 4

Kết qủa
5

Được gửi lên bởi:Jimmy
Ngày:2008-01-22
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Bạn Taek

hide comments
2016-09-05 19:53:53
time chặt quá =.=
2015-09-18 14:38:37
ng ra để chắc hs lê quý đôn@@
2015-08-07 05:21:47 Lê Quang Vũ
http://truongthptchuyenlekhiet.adu.vn/
2015-02-01 15:27:37 Anh Duc Le
time chặt, std::vector bị TLE
2013-03-06 06:03:06 Vũ Quốc Oai
1
2010-11-25 00:27:49 dhkhtn
nham low vs up T.T
2009-06-03 14:36:00 Lee Zhung Hee
http://www.thpt-lequydon-danang.edu.vn/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.