CF1307E.Cow and Treats

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.

在成功完成了一年牛奶生产后，农夫约翰正用奶牛们最爱的美食——美味的青草——来犒劳它们！

田地里有一排长度为 $n$ 的青草，每单位青草的甜度为 $s_i$。农夫约翰有 $m$ 头奶牛，第 $i$ 头奶牛喜爱的甜度为 $f_i$，饥饿值为 $h_i$。他希望从中选出两个互不相交的子集，分别安排在青草排的左侧和右侧（左右两侧的奶牛数量均无限制）。奶牛将按如下方式被喂食：

• 左侧和右侧的奶牛将轮流进食，轮次顺序由农夫约翰决定；
• 当一头奶牛进食时，它会朝另一端直线行走（方向不变），沿途只吃甜度恰好等于其喜爱甜度 $f_i$ 的青草，直到总共吃下 $h_i$ 单位青草为止；
• 一旦某头奶牛吃够了 $h_i$ 单位青草，它便立刻在当前位置睡着，从而阻挡后续所有从左或右方向经过该位置的奶牛；
• 如果一头奶牛在行进途中遇到另一头已睡着的奶牛，或抵达青草排的尽头，它就会感到沮丧。农夫约翰绝对不允许任何奶牛感到沮丧。

注意：青草不会再生长。此外，为避免奶牛沮丧，农夫约翰可选择仅让部分奶牛进食（即不必让全部奶牛都参与喂食）。

令人惊讶的是，农夫约翰发现：睡着的奶牛最满足。若农夫约翰以最优策略安排喂食顺序，最多能有多少头奶牛睡着？以及，有多少种方式选择左侧与右侧的奶牛子集（模 $10^9+7$），使得最终睡着的奶牛数量达到该最大值？只要不引起任何奶牛沮丧，农夫约翰派遣奶牛的顺序无关紧要。

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.

第一行包含两个整数 $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$ 行中，第 $i$ 行包含两个整数 $f_i$ 和 $h_i$（$1 \le f_i, h_i \le n$）—— 分别表示第 $i$ 头奶牛最喜爱的甜度值和饥饿值。任意两头奶牛不会同时具有相同的饥饿值和最喜爱的甜度值。

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

输出两个整数——最多可以有多少头奶牛在睡觉，以及对应的方案数对 $10^9+7$ 取模的结果。

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.

在第一个例子中，FJ 可以按以下方式排列奶牛，从而得到 $2$ 头正在睡觉的奶牛：

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

在第二个例子中，FJ 可以按以下方式排列奶牛，从而得到 $1$ 头正在睡觉的奶牛：

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

在第三个例子中，FJ 可以按以下方式排列奶牛，从而得到 $2$ 头正在睡觉的奶牛：

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

在第四个例子中，FJ 无法使任何奶牛进入睡眠状态，因此两侧均不会排列任何奶牛。