1762: 种植问题

现在你有一个无穷大的农田，并想在里面种植蔬菜。但你很懒，所以雇佣了n个人来帮你的忙，每个人替你在一个给定的矩形土地内播种，且这些土地可以互相覆盖，也就是说同一片土地可能被播种多次，但只有最强的种子最终将存活下来。

现在共有m种不同的种子，他们长出的蔬菜价格不同。但是，越强的种子长出的蔬菜总是越贵。现在告诉你雇佣的人帮你播种的方案，请你计算你卖掉这些蔬菜将获得的钱。

输入第一行包含两个整数n, m (1 <= n <= 30000, 1 <= m <= 3)。接下去一行包含m个不同的整数pi(1 <= pi <= 100)，按1到m的编号表示每种蔬菜的价格。接下去n行每行包含5个整数x1, y1, x2, y2, s，表示每个帮你的人替你在左下角坐标为(x1,y1)，右上角坐标为(x2,y2)的矩形内种植第s种蔬菜的种子，所有坐标值均不超过1000000。

输出只有一个数字，即你将获得的钱。

2 2

5 2

0 0 2 1 1

1 0 3 2 2

16