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$ 取模后的结果。

输入输出样例 #1

输入 #1

5 2
1 1 1 1 1
1 2
1 3

输出 #1

2 2

输入输出样例 #2

输入 #2

5 2
1 1 1 1 1
1 2
1 4

输出 #2

1 4

输入输出样例 #3

输入 #3

3 2
2 3 2
3 1
2 1

输出 #3

2 4

输入输出样例 #4

输入 #4

5 1
1 1 1 1 1
2 5

输出 #4

0 1

说明/提示

在第一个示例中，FJ 可以通过以下方式排列奶牛，使 $2$ 头奶牛睡着：

• 将奶牛 $1$ 排在左侧，奶牛 $2$ 排在右侧。
• 将奶牛 $2$ 排在左侧，奶牛 $1$ 排在右侧。

在第二个示例中，FJ 可以通过以下方式排列奶牛，使 $1$ 头奶牛睡着：

• 将奶牛 $1$ 排在左侧。
• 将奶牛 $2$ 排在左侧。
• 将奶牛 $1$ 排在右侧。
• 将奶牛 $2$ 排在右侧。

在第三个示例中，FJ 可以通过以下方式排列奶牛，使 $2$ 头奶牛睡着：

• 将奶牛 $1$ 和 $2$ 都排在左侧。
• 将奶牛 $1$ 和 $2$ 都排在右侧。
• 将奶牛 $1$ 排在左侧，奶牛 $2$ 排在右侧。
• 将奶牛 $1$ 排在右侧，奶牛 $2$ 排在左侧。

在第四个示例中，FJ 无法让任何奶牛睡着，因此两侧都不会有奶牛排列。