当前没有测试数据。

题目描述

小L有$m$元钱，商店中有$n$件商品，a[i]表示第i件商品的初始价格，每件商品有无限个。商品可能会变价格。 在t天后，求出小L最多可以赚到的钱数。当然，小L可以选择不买任何商品。

输入输出

输入

第一行三个数$n$，$m$，$t$，表示描述中的意思。 接下来$n$个数，第i个数表示a[i]。 接下来一个数$q$，表示商品变价格的次数。 接下来$q$行，每行三个数： 第i行第一个数为w[i]（<=t)，表示第几天开始变的价。 第二个数为改变价格的商品编号。 第三个数为改变的价格。

输出

一行，输出小L最多赚的钱数。

样例

输入：

5 18 5
2 7 8 3 10
5
2 2 3
2 3 8
3 2 8
3 4 10
5 5 14

输出：

48

解释：在第2天买入6个2号商品，第3天卖出，还有48元。在第三天买入4个5号商品，1个4号商品，分别于第5、第4天卖出，还有66元，利润48元。

数据规模

$n$<=10000

$m$<=1000000000

$t$<=100

$a[i]$<=1000000000