小红有 个英雄，第 个英雄的 cost 是 ，战斗力为 。另外，存在一些“双生英雄”关系，如果同时上阵某一对英雄，则可以获得额外的战斗力收益。 现在小红最多可以上阵四名英雄，且要求总 cost 不超过。小红希望你求出组队的最大战斗力。

输入描述:

第一行输入三个整数 代表英雄数量、总cost限制、双生英雄的对儿数。 此后 行，第 行输入两个正整数 代表第 个英雄的 cost 和战斗力。 此后 行，第 行输入三个正整数 代表第 和第 个英雄是双生英雄，同时上阵可以额外增加 战斗力。 除此之外，保证每个英雄最多只存在一对双生英雄关系。对于 的用例，额外保证 。

输出描述:

输出一个整数，代表组队的最大战斗力。