Trucks and Cities

题意简述 有$n$个城市坐落在一条数轴上，第$i$个城市位于位置$a_i$． 城市之间有$m$辆卡车穿行．每辆卡车有四个参数：$s_i$为起点编号，$f_i$为终点编号，$c_i$表示每行驶$1$个单位长度需要消耗的油量，$r_i$表示可以在路途中加油的次数． 当卡车到达一个城市的时候可以将油加满（当然也可以不加），在路中无法加油，但是路途中总加油次数不能超过$r_i$． 所有卡车的油箱都是一样大的，我们称它的容积为$V$．试求一个最小的$V$，使得对于所有的卡车都存在一种方案，在路途中任意时刻油箱内的油量大于等于$0$且路途中总加油次数小于等于$r_i$的情况下从起点城市到达终点城市． 输入数据 第一行两个正整数$n,m(n \leq 400 , m \leq 250000)$表示城市数量与卡车数量 接下来一行$n$个正整数$a_i(1 \leq a_i \leq 10^9 , a_i \leq a_{i+1})$描述每一个城市的位置 接下来$m$行每行四个整数$s_i,t_i,c_i,r_i(1 \leq s_i < t_i \leq n , 1 \leq c_i \leq 10^9 , 0 \leq r_i \leq n)$描述一辆卡车 输出数据 输出一行表示最小油箱容积

There are $ n $ cities along the road, which can be represented as a straight line. The $ i $ -th city is situated at the distance of $ a_i $ kilometers from the origin. All cities are situated in the same direction from the origin. There are $ m $ trucks travelling from one city to another. Each truck can be described by $ 4 $ integers: starting city $ s_i $ , finishing city $ f_i $ , fuel consumption $ c_i $ and number of possible refuelings $ r_i $ . The $ i $ -th truck will spend $ c_i $ litres of fuel per one kilometer. When a truck arrives in some city, it can be refueled (but refueling is impossible in the middle of nowhere). The $ i $ -th truck can be refueled at most $ r_i $ times. Each refueling makes truck's gas-tank full. All trucks start with full gas-tank. All trucks will have gas-tanks of the same size $ V $ litres. You should find minimum possible $ V $ such that all trucks can reach their destinations without refueling more times than allowed.

First line contains two integers $ n $ and $ m $ ( $ 2 \le n \le 400 $ , $ 1 \le m \le 250000 $ ) — the number of cities and trucks. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^9 $ , $ a_i < a_{i+1} $ ) — positions of cities in the ascending order. Next $ m $ lines contains $ 4 $ integers each. The $ i $ -th line contains integers $ 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 $ ) — the description of the $ i $ -th truck.

Print the only integer — minimum possible size of gas-tanks $ V $ such that all trucks can reach their destinations.

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

55

Let's look at queries in details: 1. the $ 1 $ -st truck must arrive at position $ 7 $ from $ 2 $ without refuelling, so it needs gas-tank of volume at least $ 50 $ . 2. the $ 2 $ -nd truck must arrive at position $ 17 $ from $ 2 $ and can be refueled at any city (if it is on the path between starting point and ending point), so it needs gas-tank of volume at least $ 48 $ . 3. the $ 3 $ -rd truck must arrive at position $ 14 $ from $ 10 $ , there is no city between, so it needs gas-tank of volume at least $ 52 $ . 4. the $ 4 $ -th truck must arrive at position $ 17 $ from $ 10 $ and can be refueled only one time: it's optimal to refuel at $ 5 $ -th city (position $ 14 $ ) so it needs gas-tank of volume at least $ 40 $ . 5. the $ 5 $ -th truck has the same description, so it also needs gas-tank of volume at least $ 40 $ . 6. the $ 6 $ -th truck must arrive at position $ 14 $ from $ 2 $ and can be refueled two times: first time in city $ 2 $ or $ 3 $ and second time in city $ 4 $ so it needs gas-tank of volume at least $ 55 $ .