← 返回题目列表

AtCoder · code_festival_2015_okinawa_i

I. 实施成瘾者

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

问题

Wolf Sothe 喜欢实现在线判断问题,他希望解决尽可能多的问题。但是,如果他每天不断地解决问题而不休息,那么一天能解决的问题数量就会一天天减少。

所以,有时 Wolf Sothe 会休息一天。在那一天,沃尔夫·索特不会解决任何问题,那么第二天和以后沃尔夫·索特就能解决问题。

Wolf Sothe一天能解决的问题数量如下:

  • 如果那天是工作日,我们将 Wolf Sothe 持续解决问题的天数定义为 k (不包括那一天)。那么 Wolf Sothe 就可以解决 max(0, A − k \times B) 当天出现问题。
  • 如果那天是休息日,那么当天就不会解决任何问题。

Wolf Sothe 想要解决问题 N 天。让 N 天按从第一天到第二天的顺序排列 N_{th} 天。假设沃尔夫·索特在第一天之前没有解决问题。

此外,我们提前知道有一些确定的休息日。

将给出所有已决定的休息日的列表。对于任何其他日期,您可以将其标记为休息日或工作日。请找出在此过程中可以解决的问题数量的最大值 N 天。


输入

输入将由以下格式的标准输入给出

N A B M
t_1
t_2
:
t_M
  • 对于第一行,整数 N(1≦N≦1,000,000,000), A(1≦A≦1,000,000,000), B(1≦B≦1,000,000,000), M(0≦M≦100,000) 将用空格分隔。 M 表示已决定的休息天数。
  • 从第二行开始有 M 附加行提供有关决定的休息日的信息。对于 i_{th} 行,一个整数 t_i(1≦t_i≦N) 代表 t_i 将给予决定的休息日。请注意,如果 i < j,那么 t_i<t_j

输出

请输出期间可以解决的问题数的最大值 N 天一线。

在输出末尾打印换行符。


输入示例 1

5 6 2 0

输出示例 1

20

假设沃尔夫·索特在第三天休息并解决剩余的问题 4 天。

  • 第一天,Wolf Sothe 一直在解决问题 0 天。因此, max(0, 6 − 0 \times 2) = 6 问题。
  • 第二天,Wolf Sothe 一直在为 1 天。因此, max(0,6 − 1 \times 2) = 4 问题。
  • 第三天,沃尔夫·索特休息。因此, 0 问题。
  • 第四天,Wolf Sothe 一直在为 0 天。因此, max(0, 6 − 0 \times 2) = 6 问题。
  • 第五天,Wolf Sothe 一直在为 1 天。因此, max(0, 6 − 1 \times 2) = 4 问题。

总之, 6 + 4 + 0 + 6 + 4 = 20 将全部解决。


输入示例 2

6 4 3 1
3

输出示例 2

13

输入示例3

12 10 3 3
2
7
10

输出示例 3

71