#383. D - 消灭怪物

D - 消灭怪物

D - 消灭怪物

题目描述

有 NN 只怪物排成一排,按从左到右的顺序编号为 11 到 NN。怪物 ii 的初始生命值为 AiA_i。

高桥拥有 MM 张卷轴,编号为 11 到 MM。

使用第 jj 张卷轴需要消耗 WjW_j 点魔力,并对编号在闭区间 [Lj,Rj][L_j,R_j] 内的每只怪物造成 CjC_j 点伤害。

高桥可以选择其中若干张卷轴,每张卷轴最多使用一次,目标是消灭所有怪物。当一只怪物受到的累计伤害大于或等于其初始生命值时,它就被消灭。

求消灭全部怪物所需的最小总魔力消耗;如果无论怎样选择卷轴都做不到,输出 -1。

输入格式

第一行输入两个整数 N,MN,M。

第二行输入 NN 个整数 A1,…,ANA_1,\ldots,A_N。

接下来 MM 行,每行输入四个整数 Lj,Rj,Cj,WjL_j,R_j,C_j,W_j。

输出格式

输出最小魔力消耗。如果无法消灭全部怪物,输出 -1。

数据范围

  • 1≤N≤2001\le N\le200
  • 1≤M≤151\le M\le15
  • 1≤Ai≤1091\le A_i\le10^9
  • 1≤Lj≤Rj≤N1\le L_j\le R_j\le N
  • 1≤Cj≤1091\le C_j\le10^9
  • 1≤Wj≤1091\le W_j\le10^9
  • 所有输入均为整数。

样例输入 1

3 3
5 10 5
1 3 5 10
2 2 5 3
1 3 10 15

样例输出 1

13

样例输入 2

4 3
10 10 10 20
1 2 10 5
2 3 10 5
3 4 10 5

样例输出 2

-1

样例输入 3

6 6
12 15 8 20 10 14
1 3 10 7
2 5 8 9
4 6 12 11
1 6 6 15
3 4 10 6
5 6 10 8

样例输出 3

39

样例输入 4

8 9
500000000 800000000 600000000 1000000000 700000000 900000000 400000000 300000000
1 4 400000000 100000000
3 8 500000000 200000000
1 8 300000000 250000000
5 7 400000000 80000000
2 5 300000000 90000000
1 2 500000000 120000000
7 8 200000000 50000000
4 6 400000000 110000000
1 8 600000000 400000000

样例输出 4

520000000

样例输入 5

1 1
1000000000
1 1 1000000000 1000000000

样例输出 5

1000000000