贝茜要和朋友们一起去滑雪。雪山上有 个路标（），按海拔从低到高依次标记为 （路标 位于山脚）。
对于每个路标 ，有一条从路标 出发，终点为路标 （）的滑雪道。这条滑道的难度为 （），乐趣值为 （）。
贝茜的 个朋友（）每人会进行如下操作：选择一个起始路标 ，然后沿着滑道向下滑行（依次经过 ，依此类推），直到抵达路标 。
每位朋友获得的乐趣值等于他们经过的所有滑道的乐趣值之和。每个朋友有不同的技能水平 （）和勇气值 （），这限制他们选择的起始路标必须满足：滑行过程中最多有 条滑道的难度超过 。
请为每位朋友计算他们能获得的最大乐趣值。
第一行包含 。
接下来 到 行，每行包含三个整数 ， 和 。
随后一行包含 。
接下来 行，每行包含两个整数 和 。
输出 行，每行对应一个朋友的答案。
注意：由于涉及大整数运算，可能需要使用 64 位整数类型（如 C/C++ 中的 long long）。
long long
4 1 20 200 2 30 300 2 10 100 8 19 0 19 1 19 2 20 0 20 1 20 2 29 0 30 0
0 300 500 300 500 500 300 500
第一位朋友只能选择路标 作为起点，因为其他路标都会导致至少经过一条难度超过 的滑道。总乐趣值为 。
第二位朋友可以选择路标 ，依次滑行至路标 和 。总乐趣值为 ，其中有一条滑道难度超过 。
第三位朋友可以选择路标 ，依次滑行至路标 和 。总乐趣值为 ，其中有两条滑道难度超过 。