三国纷争之际，诸葛亮受刘备之托，欲派遣将领出征以扩大蜀汉版图。为了让将领们在战场上能随机应变，诸葛亮准备了一系列锦囊妙计，每个锦囊都对应着不同的策略，且能在关键时刻发挥巨大作用。同时，出征的将领们需要携带一定的物资，包括武器、粮草等，以保证军队的战斗力和生存能力。然而，将领们所乘坐的战船承载重量有限，这就需要诸葛亮精心规划，合理选择锦囊和物资，以达到最佳的出征效果。

诸葛亮手中有 n 个锦囊妙计和 m 种物资可供将领们选择携带。每个锦囊妙计都有其独特的价值 v_i（1\leq i\leq n），表示该锦囊在战场上能为军队带来的额外收益，同时每个锦囊有一个占用战船空间的重量 w_i。每种物资有其数量 c_j (1 \leq  j  \leq m）、单个物资的价值 p_j（即该物资能为军队提供的收益）和单个物资占用的重量 q_j。

将领们所乘坐的战船最大承载重量为 W。诸葛亮需要在战船承载重量的限制下，为将领们挑选合适的锦囊和物资，使得这些锦囊和物资的总价值最大，帮助军队在战场上取得更好的战果。

第一行包含三个整数 n、m 和 W ，分别表示锦囊的数量、物资的种类数和战船的最大承载重量。

接下来的 n 行，每行包含两个整数 v_i 和 w_i ，表示第 i 个锦囊的价值和重量。

再接下来的 m 行，每行包含三个整数 c_j、p_j 和 q_j，表示第 j 种物资的数量、单个物资的价值和单个物资的重量。

输出一个整数，表示在战船承载重量限制下，诸葛亮为将领们挑选的锦囊和物资所能达到的最大总价值。

可以选择第一个锦囊（价值 3，重量 4），再选择两个第一种物资（每个价值 2，重量 3），总重量为 4 + 2\times3 = 10，未超过战船的最大承载重量，总价值为 3 + 2\times2 = 7。

经过分析可知，这是在重量限制下能达到的最大总价值。

30%数据：1\leq n\leq 10，1\leq m\leq 10，1\leq W\leq 100

60%数据：1\leq n\leq 500，1\leq m\leq 100，1\leq \sum p_i\leq 1500，1\leq W\leq 10000

100%数据：1\leq n\leq 1000，1\leq m\leq 200，1\leq \sum p_i\leq 30000，1\leq W\leq 100000