B - みかん Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

みかんが N 個あり、1, 2, ..., N の番号がついています。 それぞれのみかんにはちょうど A 個またはちょうど B 個の房があります。

これらのみかんの房の個数について、以下のことがわかっています。

  • 各 i (1 \leq i \leq M) について、番号が L_i 以上 R_i 以下のみかんには房がそれぞれちょうど A 個ある。

N 個のみかんの房の個数の合計として考えられる値のうち最大のものを求めてください。

制約

  • 1 \leq N \leq 100
  • 1 \leq M \leq 100
  • 1 \leq A < B \leq 100
  • 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
  • 入力値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N M A B
L_1 R_1
L_2 R_2
:
L_M R_M

出力

答えを出力せよ。

入力例 1

5 2 6 7
2 3
3 4

出力例 1

32

それぞれのみかんの房の個数が以下のようになっているとき、房の個数の合計が最大となります。

  • みかん 2, 3, 4 には房がそれぞれ A = 6 個ある。
  • みかん 1, 5 には房がそれぞれ B = 7 個ある。

このときの房の個数の合計は 6 \times 3 + 7 \times 2 = 32 となります。

入力例 2

10 3 20 30
1 6
2 7
3 10

出力例 2

200

すべてのみかんが A = 20 個の房を持ちます。

入力例 3

100 5 12 34
6 8
81 81
26 26
90 91
49 50

出力例 3

3202