F. Sign Entanglement
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Pozislav and Minuslav met at a forum on the physics of integers.

It turned out that their research areas are very similar — Pozislav studies energy emissions of positive numbers, while Minuslav studies energy bursts of negative numbers.

The guys decided to combine their efforts and conduct a large-scale study of sign entanglement:

  • Suppose that at time $$$t_i$$$ there is an energy emission on the positive half-axis.
  • Suppose that at time $$$t_j$$$ there is an energy burst on the negative half-axis.
  • If $$$0 \lt |t_i - t_j| \le d$$$, then events $$$i$$$ and $$$j$$$ are considered entangled by sign.

The guys combined their records — now they need to find the number of pairs of events that are entangled by sign.

Input

The first line contains two integers $$$n$$$ and $$$d$$$ $$$(1 \le n \le 3 \cdot 10^5; 1 \le d \le 10^9)$$$ — the number of studied energy events and the maximum time difference for entanglement to exist.

The second line contains $$$n$$$ integers $$$t_i$$$ $$$(1 \le t_i \le 10^9)$$$ — the moment in time when the $$$i$$$-th event occurred.

The third line contains a string $$$S$$$ $$$(|S| = n)$$$ — the signs of the half-axes on which the events occurred:

  • if $$$S_i$$$ is +, then the $$$i$$$-th event occurred on the positive half-axis;
  • if $$$S_i$$$ is -, then the $$$i$$$-th event occurred on the negative half-axis.

It is guaranteed that the records are given in chronological order: $$$t_1 \le t_2 \le \ldots \le t_n$$$.

Output

Output a single integer $$$T$$$ $$$(0 \le T \le 10^{18})$$$ — the number of pairs of entangled events by sign.

Example
Input
14 3
1 1 3 3 3 3 5 5 6 6 6 8 9 11
+--+++--+++++-
Output
23
Note

First test example

Events on the positive axis occurred at times $$$[1, 3, 3, 3, 6, 6, 6, 8, 9]$$$. Events on the negative axis occurred at times $$$[1, 3, 5, 5, 11]$$$.

Let's enumerate the entangled pairs of events:

  • An event at time $$$1$$$ on the positive axis and an event at time $$$3$$$ on the negative axis —- $$$1$$$ pair.
  • An event at time $$$1$$$ on the negative axis and three events at time $$$3$$$ on the positive axis — a total of $$$3$$$ pairs.
  • An event at time $$$3$$$ on the negative axis and three events at time $$$6$$$ on the positive axis — a total of $$$3$$$ pairs.
  • Three events at time $$$3$$$ on the positive axis and two events at time $$$5$$$ on the negative axis — a total of $$$6$$$ pairs.
  • Two events at time $$$5$$$ on the negative axis and three events at time $$$6$$$ on the positive axis — a total of $$$6$$$ pairs.
  • Two events at time $$$5$$$ on the negative axis and an event at time $$$8$$$ on the positive axis — a total of $$$2$$$ pairs.
  • An event at time $$$8$$$ on the positive axis and an event at time $$$11$$$ on the negative axis — a total of $$$1$$$ pair.
  • An event at time $$$9$$$ on the positive axis and an event at time $$$11$$$ on the negative axis — a total of $$$1$$$ pair.

In total, we get $$$1 + 3 + 3 + 6 + 6 + 2 + 1 + 1 = 23$$$ pairs of entangled events.