← 返回题目列表

Codeforces · 1307/E

E. 牛和零食

中文机器翻译题面 查看原题

经过一年的成功牛奶生产,农夫约翰用他们最喜欢的食物奖励他的奶牛:美味的草!

田野上有一排$$$n$$$单位的草,每块草的甜度为$$$s_i$$$。农夫约翰有 $$$m$$$ 头奶牛,每头奶牛都有最喜欢的甜味 $$$f_i$$$ 和饥饿值 $$$h_i$$$。他想挑选两个不相交的奶牛子集,在草排的左侧和右侧排成一行。两边必须有多少头牛没有限制。奶牛将按以下方式处理:

- 左右两侧的奶牛将按照农夫约翰决定的顺序轮流喂食。
- 当牛进食时,它会不改变方向朝另一端走去,吃它最喜欢的甜味草,直到吃掉 $$$h_i$$$ 单位。
- 当一头牛吃掉 $$$h_i$$$ 单位时,它就会在那里睡着,防止更多的牛从两个方向经过它。
- 如果它遇到另一头熟睡的牛或到达草排的尽头,它会感到不安。农夫约翰绝对不希望任何奶牛感到不安。

请注意,草不会再长出来。此外,为了防止奶牛不安,并不是每头奶牛都必须喂食,因为 FJ 可以选择其中的一部分。

令人惊讶的是,FJ 确定睡觉的奶牛是最满意的。如果 FJ 排序最优,则可以得到的最大睡眠牛数是多少?FJ 可以选择左侧和右侧的奶牛子集有多少种方式来实现最大睡眠牛数(模 $$$10^9+7$$$)?只要没有奶牛不高兴,FJ 发送奶牛的顺序并不重要。

输入

第一行包含两个整数 $$$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$$$ 牛最喜欢的甜度和饥饿值。没有两头牛同时具有相同的饥饿感和喜爱的甜味。

输出

输出两个整数 — 可能导致的最大睡牛数以及对 $$$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

注意

在第一个示例中,FJ 可以按如下方式将奶牛排列起来,以实现 $$$2$$$ 睡觉的奶牛:

- 牛 $$$1$$$ 排列在左侧,牛 $$$2$$$ 排列在右侧。
- 牛 $$$2$$$ 排列在左侧,牛 $$$1$$$ 排列在右侧。

在第二个示例中,FJ 可以按如下方式将奶牛排列起来,以实现 $$$1$$$ 睡觉的奶牛:

- 牛 $$$1$$$ 排列在左侧。
- 牛 $$$2$$$ 排列在左侧。
- 牛 $$$1$$$ 排列在右侧。
- 牛 $$$2$$$ 排列在右侧。

在第三个示例中,FJ 可以按如下方式排列奶牛,以实现 $$$2$$$ 睡觉的奶牛:

- 牛 $$$1$$$ 和 $$$2$$$ 排列在左侧。
- 牛 $$$1$$$ 和 $$$2$$$ 排列在右侧。
- 牛 $$$1$$$ 排列在左侧,牛 $$$2$$$ 排列在右侧。
- 牛 $$$1$$$ 排列在右侧,牛 $$$2$$$ 排列在左侧。

在第四个示例中,FJ 不会有任何正在睡觉的奶牛,因此两侧不会有奶牛排队。