#Z6024. islands 打炉石传说

islands 打炉石传说

islands 最近在玩一款游戏“炉石传说”,又名“魔兽英雄传”。炉石传说是一款卡牌类对战的游戏。游戏是两人对战,总的来说,里面的卡牌分成两类,一类是法术牌,另一类是随从牌(所谓随从就是怪物)。 为了简化问题,现在假设随从牌的作用是召唤一个具有一定攻击力的怪物,法术牌的作用是给某个随从增加一定攻击力。随从牌和法术牌的使用都需要消耗一定的法力值。现在 islands 有 10 点法力值,手上有 n 张牌(islands 最多有 10 张牌,否者他将会被爆牌 T_T),有些是法术牌,有些是随从牌。islands 现在是大劣势,他想要利用这 10 点法力值使得召唤出来的所有随从的攻击力总和最高(法力值可以不用完)。注意,任何法术牌都必须使用在某个召唤出来的随从上,也就是如果 islands 没有召唤过随从,他将不能使用任何法术牌。告诉 islands 他能召唤的随从的总攻击力最大是多少。

输入格式

每组数据首先输入一个 n(0n10n(0 \le n \le 10 ,表示 islands 有 n 张牌。

接下来 n 行,每行输入 3 个整数 cost(0cost10)d0或者1),w(w1000)cost(0 \le cost \le 10) ,d(0 或者 1),w(|w| \le 1000) 。其中 cost 表示该牌的法力值消耗,如果 d=0 ,表示该牌是攻击力为 w 的随从牌;如果 d=1 ,表示是能给一个随从增加 w 攻击的法术牌。

输出格式

输出一行表示答案。 输出时每行末尾的多余空格,不影响答案正确性 要求使用「文件输入输出」的方式解题,输入文件为 stone.in,输出文件为 stone.out 样例输入

1
1 0 100

样例输出

100