Cow and Treats

题意翻译

在一年成功的牛奶生产后，Farmer John 奖励他的奶牛们它们最喜欢的美味的草。 在田里有 $n$ 个单位的排成一行的草，每个单位的草有甜味 $s_i$。Farmer John 有 $m$ 头奶牛，每只都有最喜欢的甜味 $f_i$ 和饥饿值 $h_i$。他想要在奶牛选取两个不相交的子集，分别在这行草的左侧和右侧排成一列。注意两边站多少奶牛是无关紧要的。奶牛会按以下方式被喂： - Farmer John 会按照指定的顺序依次喂奶牛。 - 在奶牛被喂的时候，它会径直从一端走向另一端，一路上把甜味 $s_i$ 和它喜爱的甜味 $f_i$ 相同的草吃掉。 - 当它恰好吃了 $h_i$ 单位的草，它会立即在原地停止不动并睡觉，这会使得其它奶牛无法通过这个位置（不论来自哪一侧）。 - 如果一个奶牛遇到了一个睡着的奶牛或者它走到了整行草的最末尾都没有吃饱，那么它就会变得沮丧。Farmer John 绝对不想让任何奶牛变得沮丧。 注意草不会长回来。并且为了防止奶牛沮丧，Farmer John 不必保证喂了所有奶牛。 惊人的是，Farmer John 已经发现睡着的奶牛是最满足的。如果 Farmer John 安排的最优。求出最多的睡着的奶牛数，并求出在此情况下有多少种左右两侧奶牛的方案 Farmer John 可以选择（对 $10^9+7$ 取模）。只要这个方案存在一种顺序使得能不让奶牛沮丧即可，Farmer John 具体如何安排是无关紧要的。 $n,m\le 5000$. （Translated by [@Ryoku](https://www.luogu.com.cn/user/34238)）

题目描述

After a successful year of milk production, Farmer John is rewarding his cows with their favorite treat: tasty grass! On the field, there is a row of $ n $ units of grass, each with a sweetness $ s_i $ . Farmer John has $ m $ cows, each with a favorite sweetness $ f_i $ and a hunger value $ h_i $ . He would like to pick two disjoint subsets of cows to line up on the left and right side of the grass row. There is no restriction on how many cows must be on either side. The cows will be treated in the following manner: - The cows from the left and right side will take turns feeding in an order decided by Farmer John. - When a cow feeds, it walks towards the other end without changing direction and eats grass of its favorite sweetness until it eats $ h_i $ units. - The moment a cow eats $ h_i $ units, it will fall asleep there, preventing further cows from passing it from both directions. - If it encounters another sleeping cow or reaches the end of the grass row, it will get upset. Farmer John absolutely does not want any cows to get upset. Note that grass does not grow back. Also, to prevent cows from getting upset, not every cow has to feed since FJ can choose a subset of them. Surprisingly, FJ has determined that sleeping cows are the most satisfied. If FJ orders optimally, what is the maximum number of sleeping cows that can result, and how many ways can FJ choose the subset of cows on the left and right side to achieve that maximum number of sleeping cows (modulo $ 10^9+7 $ )? The order in which FJ sends the cows does not matter as long as no cows get upset.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1 \le n \le 5000 $ , $ 1 \le m \le 5000 $ ) — the number of units of grass and the number of cows. The second line contains $ n $ integers $ s_1, s_2, \ldots, s_n $ ( $ 1 \le s_i \le n $ ) — the sweetness values of the grass. The $ i $ -th of the following $ m $ lines contains two integers $ f_i $ and $ h_i $ ( $ 1 \le f_i, h_i \le n $ ) — the favorite sweetness and hunger value of the $ i $ -th cow. No two cows have the same hunger and favorite sweetness simultaneously.

输出格式

Output two integers — the maximum number of sleeping cows that can result and the number of ways modulo $ 10^9+7 $ .

输入输出样例

输入样例 #1

5 2
1 1 1 1 1
1 2
1 3

输出样例 #1

2 2

输入样例 #2

5 2
1 1 1 1 1
1 2
1 4

输出样例 #2

1 4

输入样例 #3

3 2
2 3 2
3 1
2 1

输出样例 #3

2 4

输入样例 #4

5 1
1 1 1 1 1
2 5

输出样例 #4

0 1

说明

In the first example, FJ can line up the cows as follows to achieve $ 2 $ sleeping cows: - Cow $ 1 $ is lined up on the left side and cow $ 2 $ is lined up on the right side. - Cow $ 2 $ is lined up on the left side and cow $ 1 $ is lined up on the right side. In the second example, FJ can line up the cows as follows to achieve $ 1 $ sleeping cow: - Cow $ 1 $ is lined up on the left side. - Cow $ 2 $ is lined up on the left side. - Cow $ 1 $ is lined up on the right side. - Cow $ 2 $ is lined up on the right side. In the third example, FJ can line up the cows as follows to achieve $ 2 $ sleeping cows: - Cow $ 1 $ and $ 2 $ are lined up on the left side. - Cow $ 1 $ and $ 2 $ are lined up on the right side. - Cow $ 1 $ is lined up on the left side and cow $ 2 $ is lined up on the right side. - Cow $ 1 $ is lined up on the right side and cow $ 2 $ is lined up on the left side. In the fourth example, FJ cannot end up with any sleeping cows, so there will be no cows lined up on either side.