← 返回题目列表

AtCoder · code_festival_2018_quala_b

B. 蜜柑

中文机器翻译题面 查看原题

配点 : 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