← 返回题目列表

Codeforces · 1101/F

F. 卡车和城市

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

沿路有$$$n$$$个城市,可以用一条直线表示。第 $$$i$$$ 城市距离原点 $$$a_i$$$ 公里。所有城市都位于原点的同一方向。有 $$$m$$$ 卡车从一个城市行驶到另一个城市。

每辆卡车可以用$$$4$$$整数来描述:出发城市$$$s_i$$$,结束城市$$$f_i$$$,燃油消耗$$$c_i$$$和可能加油的次数$$$r_i$$$。第 $$$i$$$ 卡车每公里将消耗 $$$c_i$$$ 升燃油。

当卡车到达某个城市时,可以加油(但在偏僻的地方加油是不可能的)。第 $$$i$$$ 卡车最多可以加油 $$$r_i$$$ 次。每次加油都会使卡车的油箱充满。所有卡车启动时油箱都是满的。

所有卡车都将配备相同尺寸 $$$V$$$ 升的油箱。您应该找到尽可能少的$$$V$$$,以便所有卡车都可以到达目的地,而加油次数不会超过允许的次数。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 400$$$, $$$1 \le m \le 250000$$$) — 城市和卡车的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$, $$$a_i < a_{i+1}$$$) — 按升序排列的城市位置。

接下来的 $$$m$$$ 行每行包含 $$$4$$$ 个整数。第 $$$i$$$ 行包含整数 $$$s_i$$$、$$$f_i$$$、$$$c_i$$$、$$$r_i$$$ ($$$1 \le s_i < f_i \le n$$$, $$$1 \le c_i \le 10^9$$$, $$$0 \le r_i \le n$$$) — 的描述第 $$$i$$$ 卡车。

输出

打印唯一的整数 - 油箱 $$$V$$$ 的最小可能大小,以便所有卡车都能到达目的地。

示例

输入 #1

7 6
2 5 7 10 14 15 17
1 3 10 0
1 7 12 7
4 5 13 3
4 7 10 1
4 7 10 1
1 5 11 2

输出 #1

55

注意

让我们详细看看查询:

1、$$$1$$$-st卡车必须从$$$2$$$到达$$$7$$$位置且无需加油,因此需要至少$$$50$$$油箱容积。
2、第$$$2$$$-nd卡车必须从$$$2$$$到达$$$17$$$位置,并且可以在任意城市加油(如果在起点和终点之间的路径上),因此需要至少$$$48$$$的油箱。
3. $$$3$$$-rd卡车必须从$$$10$$$到达位置$$$14$$$,中间没有城市,所以需要至少$$$52$$$的油箱。
4. 第 $$$4$$$ 卡车必须从 $$$10$$$ 到达位置 $$$17$$$ 并且只能加油一次:最好在第 $$$5$$$ 城市(位置 $$$14$$$)加油,因此需要至少 $$$40$$$ 的油箱。
5. 第 $$$5$$$ 卡车具有相同的描述,因此它也需要容量至少为 $$$40$$$ 的油箱。
6. 第 $$$6$$$ 卡车必须从 $$$2$$$ 到达 $$$14$$$ 位置,并且可以加油两次:第一次在城市 $$$2$$$ 或 $$$3$$$ 和第二次在城市 $$$4$$$,因此需要至少 $$$55$$$ 的油箱。