成都是一座来了就不想走的城市。还因为成都是一座旅游城市。旅游景点有：古堰流碧、祠堂柏森、青城叠翠、草堂喜雨、西岭晴雪、江楼修竹、文殊朝钟、天台夕晖、青羊花会、宝光普照、…。

旅游公司为喜欢旅游的李老师提供了n个景点，每个景点有一个旅游价值w(|w|<=1000)。

旅游价值越大的景点，花费也越大。因旅游经费的问题，李老师决定：选择不超过第k(1<=k<=n)大旅游价值的景点，并且最多m(1<=m<=n-k+1)个景点旅游，使得旅游价值和最大。
       李老师想知道p(p<=n)组k和m，每组旅游价值和最大是多少？

第1行，一个整数n，表示景点的个数

第2行，由空格隔开n个整数,表示n个景点的旅游价值。

第3行，整数p，如题所述

第4~3+p行，每行由空格隔开的两整数k和m,如题所述。

该文件有p行，每行一个最大旅游价值和。

【样例解释】

答案16：选择景点1、景点3、景点4、景点5。旅游价值第1大的景点是景点4、旅游价值第2大的景点是景点1、旅游价值第3大的景点是景点3、旅游价值第4大的景点是景点5。其旅游价值和为16 。

答案5：选择景点1。旅游价值第2大的景点是景点1。其旅游价值为5。

答案1：选择景点5。旅游价值第4大的景点是景点5，旅游价值第5大的景点是景点2，但价值为-1。所以只选景点5，其旅游价值为1。

答案0：一个景点也不选。旅游价值第5大的景点是景点2，但价值为-1。选了景点2，会使旅游价值变为-1，不选则旅游价值为0。

【数据范围】

30%: n<=10。

80%:n<=3000。

100%:n <=100000。