关二哥被吕蒙打败后，壮烈牺牲。作为大哥的刘玄德，准备挑选蜀国的精锐兵力对吴国进行打击！

所以刘玄德准备在蜀国进行多轮招兵，每次刘备将对区域[l,r]的范围内招收士兵，区域内会提供一定的兵员给刘备，征召员在l,r的区域内移动，所以需要耗费r-l+1的体力，招到到区域内\sum_l^r{a_i}的兵源；

玄德发起了m次征召（由于青壮年的限制，刘备将发起不多于1000次的征召），刘备征召员的总体力是V，那么请你帮忙计算一下，刘备最多能招多少士兵！

数字n,m,v表示蜀国的士兵分布区域n，发起了m轮征兵，刘备动员能力为v；

接下来一行n个数字a_i，表示区域内在此轮征兵中能提供的士兵。

接下来m行，表示刘备每次征兵范围l,r；

如果区域被重复征兵，默认该地区又可以提供a_i的兵力；

一个数字T，表示刘备伐吴能出动的最大兵力

样例说明：

3次征兵，分别是[3,6],[5,15],[3,12]，动员能力是8，所以刘备选择第二次和第三次的区域进行征兵，动员的总兵力是27；

40\%的数据：n,m\leq 100

100\%的数据：n \leq 10^5,q \leq 1000,a_i\leq 5,V \leq 10^5