CF1307E Cow and Treats

在成功完成一年的牛奶生产后， FJ 决定用奶牛们最爱的美味青草来犒劳它们！ 草地上有一排由 $n$ 个单位组成的青草带，每单位青草的甜度为 $s_i$。 FJ 有 $m$ 头奶牛，每头奶牛有最爱的甜度 $f_i$ 和饥饿值 $h_i$。他计划挑选两个互不相交的奶牛子集，分别排列在青草带的左右两侧。两侧的奶牛数量没有限制。这些奶牛将按照以下规则进食： - 左右两侧的奶牛将按照 FJ 决定的顺序轮流进食。 - 当一头奶牛进食时，它会沿固定方向（不改变方向）前进，并吃掉甜度为 $f_i$ 的青草，直到吃够 $h_i$ 单位为止。 - 当奶牛吃够 $h_i$ 单位青草时，它会立即在该位置入睡，此后其他奶牛无法从任何方向越过它。 - 如果在前进过程中遇到另一头睡着的奶牛或到达青草带的尽头，这头奶牛就会变得烦躁。 FJ 绝对不希望任何奶牛出现烦躁情绪。 注意青草被吃掉后不会再生。此外，为了避免奶牛烦躁， FJ 可以只选择部分奶牛参与进食。 令人惊讶的是，FJ 发现睡着的奶牛满意度最高。在最优安排下，最多能有多少头奶牛入睡？为了实现这个最大入睡数量， FJ 有多少种选择左右两侧奶牛子集的方式（结果对 $10^9+7$ 取模）？只要不引发奶牛烦躁，奶牛的具体派遣顺序不影响计数。 Translated by DeepSeek.

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 5000$，$1 \le m \le 5000$）——分别表示青草的单位数量和奶牛的数量。 第二行包含 $n$ 个整数 $s_1, s_2, \ldots, s_n$（$1 \le s_i \le n$）——表示每单位青草的甜度值。 接下来的 $m$ 行，每行包含两个整数 $f_i$ 和 $h_i$（$1 \le f_i, h_i \le n$）——表示第 $i$ 头奶牛最喜欢的甜度和饥饿值。**任意两头奶牛不会同时具有相同的 $f_i$ 和 $h_i$。**

输出两个整数：能够入睡的奶牛的最大数量，以及达到该最大值的方案数对 $10^9+7$ 取模后的结果。

在第一个示例中，FJ 可以通过以下方式排列奶牛，使 $2$ 头奶牛睡着： - 将奶牛 $1$ 排在左侧，奶牛 $2$ 排在右侧。 - 将奶牛 $2$ 排在左侧，奶牛 $1$ 排在右侧。 在第二个示例中，FJ 可以通过以下方式排列奶牛，使 $1$ 头奶牛睡着： - 将奶牛 $1$ 排在左侧。 - 将奶牛 $2$ 排在左侧。 - 将奶牛 $1$ 排在右侧。 - 将奶牛 $2$ 排在右侧。 在第三个示例中，FJ 可以通过以下方式排列奶牛，使 $2$ 头奶牛睡着： - 将奶牛 $1$ 和 $2$ 都排在左侧。 - 将奶牛 $1$ 和 $2$ 都排在右侧。 - 将奶牛 $1$ 排在左侧，奶牛 $2$ 排在右侧。 - 将奶牛 $1$ 排在右侧，奶牛 $2$ 排在左侧。 在第四个示例中，FJ 无法让任何奶牛睡着，因此两侧都不会有奶牛排列。