[Spoj] NKBUS

Đề bài: http://vn.spoj.com/problems/NKBUS/
Một xe buýt của công ty có nhiệm vụ đón nhân viên đến trụ sở làm việc. Trên hành trình, xe buýt sẽ tiếp nhận nhân viên đứng chờ ở các điểm hẹn nếu như xe còn chỗ trống. Xe buýt có thể đỗ lại để chờ những công nhân chưa kịp đến điểm hẹn.
Cho biết thời điểm mà mỗi nhân viên đế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 nhân viên có thể được đến trụ sở. 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ụ sở làm việc của công ty) và số nguyên k là số lượng nhân viên đế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 nhân viên.
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ố nhân viên không vượt quá 200000.
Kết quả không vượt quá 231-1.
Ví dụ
Dữ liệu mẫu
3 2
3 2 4 3
1 3 6 3 7
5 1 5
Kết qủa
10
Giải thích: Trên đường đến công ty có 3 trạm xe buýt. Từ trạm 1 đến trạm 2, trạm 2 đến trạm 3, và từ trạm 3 đến công ty lần lượt mất 3, 1 và 5 đơn vị thời gian. Xe buýt có thể đi như sau: đến thẳng trạm 2, đón người thứ 2, đến trạm 3, chờ 1 đơn vị thời gian để đón người duy nhất ở trạm này, và cuối cùng đến công ty. Tổng cộng xe buýt đi mất 3 + 1 + 1 + 5 = 10 đơn vị thời gian.
————————-

Đầu tiên nhận thấy là đằng nào xe cũng đi từ trạm 1 -> n + 1 nên thời gian bằng tổng tất cả thời gian mà xe đi từ 1-> n + 1.
Nhận xét thấy với mỗi hành khách đến trạm i thì có thể đến trước hoặc sau khi xe buýt tới trạm i nên ta có một cái mảng W[] tức là thời gian mà xe buýt phải chờ người thứ j của trạm i và W[l] sẽ bằng thời gian người khách thứ l (khách thứ j tại trạm i) đến trạm i trừ cho thời gian xe buýt đi từ trạm 1 tới trạm i (Nếu nhỏ hơn 0 thì coi như = 0 ).
Sắp xếp w tăng dần. Sau khi sắp xêp ta có w[l] là thời gian xe chờ người thứ l và cũng là thời gian xe chời đủ l người
Cuối cùng chỉ việc so sánh số hành khách và m cái nào nhỏ hơn thì ta lấy kết quả cộng thêm cho W[] tại đó.