给定一个有 个点， 条边的有向图。 图中第 个点的价值是 ，每条边有一个代价 ，不同的边代价可能不一样。 一共有 个询问，每次询问包含两个数字 ，表示查询问从点 出发，经过代价总和不超过 的边所能到达的点的价值总和的最大值。 如果一个点被多次经过，那么其价值要计算多次。 初始节点的价值也要计算进去。

输入描述:

输入的第一行包含三个由空格隔开的正整数 。接下来的一行包括 个由空格隔开的非负整数 表示编号从小到大所有点的价值。接下来的 行每行包含三个由空格隔开的正整数 ，表示存在一条从 到 代价为 的有向边。接下来的 行每行包含两个由空格隔开的非负整数 。数据范围：

输出描述:

对于每次询问输出一个数，表示相应地答案。