You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

天才小金非常喜欢购物，他尤其喜欢那种横扫一片商店的快感。最近, 他打算对南门口的商店实行他疯狂的购物计划。南门口的商业区中最繁华的就是黄兴路步行街了。

这条街上有 $n$ 个商店，小金计划扫荡 $m$ 次，每次小金会把区间 $[l_i, r_i]$ 的每个商店扫荡一空。经过这次扫荡，小金会获得该区间内每一段连续未被扫荡的商店的 $happy$ 值的和的平方和，已经被扫荡过的商店不会重复计算。举个栗子：

现在小金想要计算：经过对购物计划的排序后，他最多获得总计多少的 $happy$ 值？

输入格式

第一行两个整数，$n, m$ ；

第二行 $n$ 个整数，第 $i$ 个数表示 $happy_i$ ；

接下来 $m$ 行，每行两个数 $li, ri$ ，表示一次行动。

输出格式

一行一个整数，表示最大的 happy 值之和。

输入样例

14 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1
4 9
2 12

输出样例

121

数据范围

对于 $30 \%$ 的数据，$n ≤ 10, m ≤ 8 。$

对于 $60 \%$ 的数据，$n ≤ 1000, m ≤ 1000 。$

对于 $100 \%$ 的数据，$n ≤ 5000, m ≤ 10^6, happy_i ≤ 100 。$