题号：NC14719
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld
题目描述
ZZZZone是一个特别喜欢甜食的人。有一天，他得到了n个糖果盒子，每个盒子里都有无穷个糖果，每个盒子里的糖果都有固定的甜蜜值。
为了获得更多的甜蜜值，ZZZZone列出了m个方案：每个方案中都有一个L 、R，ZZZZone会从第L个盒子到第R个盒子这连续的R - L + 1 个盒子中，每个盒子里拿出一颗糖吃掉，来获得甜蜜值。
每个方案最多只能实现一次，当然也可以不实现，那么，ZZZZone可以获得的最大甜蜜值是多少？
输入描述:
第一行，一个整数n，表示有n个糖果盒子 (n <= 10000)
第二行包含n个整数，表示从下标为1到n的盒子的甜蜜值(-10000 <= wi <= 10000)
第三行包含一个整数m表示方案数 (m <= 10000)
接下来m行，每行两个整数L， R (1 <= L, R <= n)
输出描述:
输出一行，包含一个整数表示最大的甜蜜值.
示例1
说明
第一个方案从1到5可得到3的甜蜜值，第二个可以得到-1的甜蜜值（此时当然不会选这个方案），所以最大可得到3的甜蜜值