F. Секретные письма
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Винни-Пух и Пятачок договорились писать друг другу секретные письма про самые важные события за день. В день происходит $$$n$$$ событий: в момент времени $$$t_i$$$ с участником $$$p_i$$$ ($$$p_i$$$ равно либо W, либо P, что обозначает Винни-Пуха и Пятачка соответственно) что-то происходит, и он должен немедленно написать об этом другому, пока всё не забыл. Написанное сообщение надо сразу отправить одним из двух способов:

  • Попросить Сову доставить письмо напрямую получателю. Каждый раз за свои услуги Сова попросит $$$d$$$ желудей.
  • Оставить письмо на хранение в норе у Кролика. Кролик дорожит свободным местом в своей норе, поэтому хранить письмо в период времени длины $$$T$$$ будет стоить $$$c \cdot T$$$ желудей. Забрать письмо от Кролика получатель сможет, когда в следующий раз сам захочет оставить у него письмо, либо в момент времени $$$t_{n + 1}$$$, когда все придут к Кролику на чай. Забирать письма в какие-либо другие моменты времени нельзя (иначе Кролик что-то заподозрит). У Кролика можно одновременно хранить сколько угодно писем, оплачивая хранение каждого по отдельности.

Помогите друзьям определить наименьшее количество желудей, которое потребуется для успешного обмена всеми письмами.

Входные данные

В первой строке записано три целых числа $$$n, c, d$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq c \leq 10^2$$$, $$$1 \leq d \leq 10^8$$$) — количество сообщений, стоимость хранения письма у Кролика, и стоимость доставки сообщения Совой.

Следующие $$$n$$$ строк описывают события. В $$$i$$$-й из этих строк записано целое число $$$t_i$$$ и символ $$$p_i$$$ ($$$0 \leq t_i \leq 10^6$$$, $$$p_i$$$ либо W, либо P) — время, в которое происходит $$$i$$$-е событие, и с кем это событие происходит.

В последней строке записано одно целое число $$$t_{n + 1}$$$ ($$$0 \leq t_{n+1} \leq 10^6$$$) — время, в которое все соберутся к Кролику на чай и заберут оставшиеся у Кролика письма.

Гарантируется, что $$$t_i < t_{i + 1}$$$ для всех $$$i$$$ от $$$1$$$ до $$$n$$$.

Выходные данные

Выведите одно целое число — минимальное общую стоимость доставки.

Примеры
Входные данные
5 1 4
0 P
1 W
3 P
5 P
8 P
10
Выходные данные
16
Входные данные
10 10 94
17 W
20 W
28 W
48 W
51 P
52 W
56 W
62 P
75 P
78 P
87
Выходные данные
916
Примечание

Одно из оптимальных решений в первом примере:

  • В момент 0 Пятачок оставляет письмо Кролику.
  • В момент 1 Винни оставляет Кролику своё письмо и забирает письмо Пятачка. Поскольку это письмо пролежало у Кролика с момента 0 по 1, это стоит $$$1$$$ желудь.
  • В момент 3 Пятачок отправляет письмо с Совой, это стоит $$$4$$$ желудя.
  • В момент 5 Пятачок оставляет письмо у Кролика и забирает письмо Винни, за которое надо заплатить 4 желудя.
  • В момент 8 Пятачок оставляет Кролику еще одно письмо.
  • В момент 10 Винни приходит к Кролику на чай и забирает два письма Пятачка, за которые надо заплатить 5 и 2 желудя соответственно.

Таким образом, общая стоимость равна $$$1 + 4 + 4 + 5 + 2 = 16$$$ желудей.