スレッド: HTTP://vn.spoj.com/problems/NKBUS/
バス会社の従業員がオフィスをピックアップする任務. 旅に, スペースがまだ使用可能の車であればバスはランデブーで待機しているスタッフがかかります. バスは、労働者がこれまでのランデブーに到達するのを待って駐車することができます.
時間を示していることを自分のランデブーポイントに各従業員とバスの運行スケジュールのすべてのポイント. 仮定すると、その時の最初のランデブーへのバス 0 そして、バスの時刻が近くにありました 0.
バスは本社に可能な限り最高のスタッフの数を運ぶために必要があります. ジョブバスを行うために最短の時間を特定してください.

上のデータ
最初の行が含まれています 2 整数n, m次は、バスの座席のランデブーと数であります
次のn行のi番目の行は、tiはi番目の+ 1をランデブーするバスi番目のランデブーから移動させるのに必要な時間である整数を含みます (n + 1のミーティングポイントは、会社の事務所となります) 整数kは私のランデブーする従業員の数であり、, 次のkの整数は、k個のスタッフのランデブーする時間です.
出力します
単一行で構成, 見つけるために最短時間.
リミット
1 ≤N≤ 200000, 1 ≤M≤ 20000
従業員の合計数が超えていません 200000.
結果が達成されません 231-1.
例
標本データ
3 2
3 2 4 3
1 3 6 3 7
5 1 5
出力します
10
説明: 会社に向かう途中で 3 バス. 駅から 1 駅へ 2, 駅 2 駅へ 3, 駅から 3 企業は失うことに向けます 3, 1 と 5 単位時間. 次のようにバスは行くことができます: 駅へのストレート 2, 歓迎会 2, 駅へ 3, 待ちます 1 この駅で唯一の人をキャッチする単位時間, そして最終的に会社に. 離れて合計バス 3 + 1 + 1 + 5 = 10 単位時間.
————————-

まず、とにかく車に気づき、駅から行きます 1 -> N + 1 万一車が1-行く時までにすべての時間の合計> N + 1.
レビューステーションに各乗客のための参照私はWいかだを持っている必要があり、私は次のバスステーションの前または後に来るかもしれません[] すなわちバスをW番目の駅iとjのを待たなければならない時間[L] 時間の訪問者l番目に等しくなります (駅iにおけるjの訪問者) 駅からのバス移動時間を除いて私は駅 1 ステーションIへ (小さい場合 0 =とみなされています 0 ).
W昇順で並べ替え. 配置した後、私たちはwを持っています[L] 二回目のLは車を待っていると、時間の車の人はLをシーソーされます
最後に、単純に我々は結果がWに追加取り、乗客数と小さい1メートルを比較[] そこ.