花环(flow)

题目描述

新年就要到了，小 Y 收到了小 L 的花环，很开心，于是决定给他的好朋友小 T 也送一些花。

一个花环可以由一个小写字母字符串 $s$ 所表示，$s_i$ 表示第 $i$ 朵花花的颜色。

小 L 送给小 Y 的是一个长度为 $n$ 的花环，小 Y 准备从上面剪下一个连续段送给小 T （注意不能全剪下来）。

小 Y 认为如果剪下的部分里，某一种颜色的花过多或者过少都会导致不美观。于是他提出了 $k$ 个限制，每个限制形如 $c, l, r$，表示颜色为 $c$ 的花的个数必须在 $[l,r]$ 之间。

然而小 Y 又发现，这些限制全都满足反而会显得不自然，于是他要求满足的限制个数必须在 $[L,R]$ 之间。

现在小 Y 想知道，有多少种不同的方案使得剪下的花环是满足条件的。

我们认为两种方案是不同的，当且仅当剪下来的部分在原花环的位置不一样。

输入格式

第一行两个正整数 $n, k$ 表示花环的长度和限制个数。

第二行一个长度为 $n$ 的字符串表示花环，保证只由小写字母组成。

之后 $k$ 行，每行一个小写字母 $c$ 和两个非负整数 $l,r$，表示一个限制。

最后一行两个非负整数 $L,R$，表示剪下的花环应该满足多少个限制。

输出格式

一行一个非负整数，表示答案。

样例输入 1

3 2
aba
a 1 2
b 1 1
1 1

样例输出 1

4

【样例解释】

合法的方案有 a（第 $1$ 个位置），a （第 $3$ 个位置），aa （第 $3$ 和第 $1$ 个位置），b（第 $2$ 个位置）。

其中前 $3$ 种方案只满足第 $1$ 个限制，最后一种方案只满足第 $2$ 个限制，故输出 4。

样例输入 2

7 3
abcbaba
a 2 3
b 0 1
c 1 1
1 2

样例输出 2

40

数据范围

对于所有数据，$ 1\leq n \leq 10^5$，$1 \leq k \leq 500$，$0 \leq L\leq R\leq k$，$0\leq l \leq r\leq n$。输入的字符串以及 $c$ 都只包含小写字母。

subtask1(10pts)：$L=0$，$R=k$。
subtask2(20pts)：$n,k\leq 300$。
subtask3(20pts)：$n \leq 5000$。
subtask4(20pts)：$L=R=k$。
subtask5(30pts)：无特殊限制。