F. Знаковая спутанность
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Позислав и Минуслав пересеклись на форуме по физике целых чисел.

Выяснилось, что их области исследований очень схожи — Позислав изучает энергетические выбросы положительных чисел, а Минуслав — энергетические всплески отрицательных чисел.

Ребята решили объединить свои усилия и провести масштабное исследование знаковой спутанности:

  • Допустим, что в момент времени $$$t_i$$$ происходит энергетический выброс на положительной полуоси.
  • Допустим, что в момент времени $$$t_j$$$ происходит энергетический всплеск на отрицательной полуоси.
  • Если $$$0 \lt |t_i - t_j| \le d$$$, то события $$$i$$$ и $$$j$$$ считаются cпутанными по знаку.

Ребята объединили свои записи — теперь им остаётся найти количество пар спутанных по знаку событий.

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

В первой строке даны два целых числа $$$n$$$ и $$$d$$$ $$$(1 \le n \le 3 \cdot 10^5; 1 \le d \le 10^9)$$$ — количество исследованных энергетических событий и наибольшая разница во времени для существования спутанности.

Вторая строка содержит $$$n$$$ целых чисел $$$t_i$$$ $$$(1 \le t_i \le 10^9)$$$ — момент времени, когда произошло $$$i$$$-е событие.

Третья строка содержит строку $$$S$$$ $$$(|S| = n)$$$ — знаки полуосей, на которых произошли события:

  • если $$$S_i$$$ равно +, то $$$i$$$-е событие произошло на положительной полуоси;
  • если $$$S_i$$$ равно -, то $$$i$$$-е событие произошло на отрицательной полуоси.

Гарантируется, что записи даны в хронологическом порядке: $$$t_1 \le t_2 \le \ldots \le t_n$$$.

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

Выведите единственное целое число $$$T$$$ $$$(0 \le T \le 10^{18})$$$ — количество пар спутанных по знаку событий.

Пример
Входные данные
14 3
1 1 3 3 3 3 5 5 6 6 6 8 9 11
+--+++--+++++-
Выходные данные
23
Примечание

Первый тестовый пример

События на положительной оси произошли в моменты времени $$$[1, 3, 3, 3, 6, 6, 6, 8, 9]$$$. События на отрицательной оси произошли в моменты времени $$$[1, 3, 5, 5, 11]$$$.

Перечислим спутанные пары событий:

  • Событие в момент времени $$$1$$$ на положительной оси и событие в момент времени $$$3$$$ на отрицательной оси —- $$$1$$$ пара.
  • Событие в момент времени $$$1$$$ на отрицательной оси и три события в момент времени $$$3$$$ на положительной оси — всего $$$3$$$ пары.
  • Событие в момент времени $$$3$$$ на отрицательной оси и три события в момент времени $$$6$$$ на положительной оси — всего $$$3$$$ пары.
  • Три события в момент времени $$$3$$$ на положительной оси и два события в момент времени $$$5$$$ на отрицательной оси — всего $$$6$$$ пар.
  • Два события в момент времени $$$5$$$ на отрицательной оси и три события в момент времени $$$6$$$ на положительной оси — всего $$$6$$$ пар.
  • Два события в момент времени $$$5$$$ на отрицательной оси и событие в момент времени $$$8$$$ на положительной оси — всего $$$2$$$ пары.
  • Событие в момент времени $$$8$$$ на положительной оси и событие в момент времени $$$11$$$ на отрицательной оси — всего $$$1$$$ пара.
  • Событие в момент времени $$$9$$$ на положительной оси и событие в момент времени $$$11$$$ на отрицательной оси — всего $$$1$$$ пара.

Суммарно получаем $$$1 + 3 + 3 + 6 + 6 + 2 + 1 + 1 = 23$$$ пары спутанных событий.