0013 - Palembang Bridges

時間制限 2 秒 / メモリ制限 256 MB / 得点 100 / Writer root / x 1 / 統計 /

TLE
2sec
MLE
256MB
得点
100

課題(Description)

パレンバン市はムシ川により 2 つの地区に分けられている．それらを地区 A と地区 B と呼ぶ．

それぞれの地区には，1,000,000,001 軒の建物がムシ川に沿って建てられており，建物には順に 0 から 1,000,000,000 までの番号が付けられている．隣りの建物との距離は，すべて，1 単位距離である．また，ムシ川の幅は 1 単位距離である．地区 A の建物 i の場所は，地区 B の建物 i の場所の川を挟んだちょうど反対側である．

パレンバン市には N 人の市民が住み，仕事をしている．市民 i の住居は地区 Pi の建物 Si にある．また，市民 i の職場は地区 Qi の建物 Ti にある．市民が住居から職場に向かう際に川を横断する場合は，船に乗らなければならない．これは不便であるので，政府は，市民が車で通勤できるように，川を横断する橋を高々 K 本建設することを決定した．橋は 2 つの地区の川を挟んだ反対側にある建物を結ぶように建設される．橋は川と垂直に建設しなければならない．橋と橋が重なってはいけない．

政府が K 本の橋を建設した後において，市民 i が住居から職場まで車で通勤する際の移動距離の最小値を Di とおく．合計 D1 + ・・・ + DN が最小となるように政府が橋を建設するのを助けてほしい．

入力形式(Input Format)

1 行目には，2 つの整数 K, N が書かれている．続く N 行のうちのそれぞれには，4 個の項目 Pi, Si, Qi, Ti が書かれている．

出力形式(Ouput Format)

移動距離の合計の最小値を 1 行で出力せよ．

入力例1(Sample Input 1)

1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

出力例1(Sample Output 1)

24

入力例2(Sample Input 2)

2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

出力例2(Sample Output 2)

22

説明(Explanation)

以下の図は 2 つの入力例を図示したものである．

以下の図は入力例 1 の解答例である．桃色の縦線が橋を表す．

以下の図は入力例 2 の解答例である．

小課題(Subtasks)

すべての入力データは以下の条件を満たす.

  • Pi, Qi は文字 ‘A’ または文字 ‘B’ である．
  • 0 ≤ Si ≤ 1,000,000,000.
  • 0 ≤ Ti ≤ 1,000,000,000.
  • 同じ建物の中に複数の住居や職場 (あるいはその両方) があるかもしれない.

    • 小課題 1 (Subtask 1) [8 点]

    • K = 1
    • 1 ≤ N ≤ 1,000

    小課題 2 (Subtask 2) [14 点]

    • K = 1
    • 1 ≤ N ≤ 100,000

    小課題 3 (Subtask 3) [9 点]

    • K = 2
    • 1 ≤ N ≤ 100

    小課題 4 (Subtask 4) [32 点]

    • K = 2
    • 1 ≤ N ≤ 1,000

    小課題 5 (Subtask 5) [37 点]

    • K = 2
    • 1 ≤ N ≤ 100,000