Monkeyland es una recta numérica infinita con $n$ monos, numerados del 1 al $n$. El $i$-ésimo mono se encuentra inicialmente en la posición $p[i]$ de la recta numérica. Es posible que varios monos compartan la misma posición inicial.
Pan puede hacer que cada mono se mueva con su hechizo encantador. La forma en que se mueve cada mono está determinada por una cadena $d$ de longitud $n$, donde cada carácter es L o R. Sea $d[i]$ el $i$-ésimo carácter de $d$.
Una vez lanzado el hechizo, el $i$-ésimo mono se mueve de la siguiente manera:
- Si $d[i] = \text{L}$, se mueve a la izquierda una posición.
- Si $d[i] = \text{R}$, se mueve a la derecha una posición.
Cada día, Pan lanzará su hechizo exactamente una vez. Si dos monos están en la misma posición en cualquier día (incluso inicialmente), se vuelven amigos. Si Pan lanzara su hechizo durante $k$ días, determine el número de pares de monos que se volverán amigos.
Entrada
Su programa debe leer desde la entrada estándar.
La primera línea de la entrada contiene dos enteros separados por espacios $n$ y $k$.
La segunda línea de la entrada contiene $n$ enteros separados por espacios $p[1], p[2], \dots, p[n]$.
La tercera línea de la entrada contiene una cadena $d$ de $n$ caracteres $d[1], d[2], \dots, d[n]$.
Salida
Su programa debe imprimir a la salida estándar.
Imprima un solo entero, el número de pares de monos que se volverán amigos.
La salida debe contener únicamente un solo entero. No imprima ningún texto adicional como Enter a number o The answer is.
Subtareas
Para todos los casos de prueba, la entrada satisfará los siguientes límites:
- $1 \le n \le 200\,000$
- $1 \le k \le 10^9$
- $1 \le p[i] \le 10^9$ para todo $1 \le i \le n$
- $d[i]$ es L o R para todo $1 \le i \le n$
Su programa será probado en instancias de entrada que satisfagan las siguientes restricciones:
| Subtarea | Puntuación | Restricciones adicionales |
|---|---|---|
| 0 | 0 | Casos de prueba de ejemplo |
| 1 | 6 | $n = 2$ |
| 2 | 13 | $d[1] = d[2] = \dots = d[n]$ |
| 3 | 10 | $n, k \le 200$ |
| 4 | 22 | $n, k \le 3000$ |
| 5 | 18 | $n \le 3000$ |
| 6 | 31 | Sin restricciones adicionales |
Ejemplos
Entrada 1
2 1 1 3 RL
Salida 1
1
Entrada 2
5 67 1 2 3 4 5 RRRRR
Salida 2
0
Entrada 3
6 7 1 1 8 16 18 22 RRLRLL
Salida 3
3
Entrada 4
10 30 9 46 27 8 12 100 56 96 6 7 LRLRRLRRLR
Salida 4
5
Entrada 5
4 2 3 4 4 6 LLRL
Salida 5
2