王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件。 主件可以没有附件，至多有 个附件。附件不再有从属于自己的附件。如果要买归类为附件的物品，必须先买该附件所属的主件，且每件物品只能购买一次。 王强查到了每件物品的价格，而他只有 元的预算。为了先购买重要的物品，他给每件物品规定了一个重要度，用整数 表示。他希望在花费不超过 元的前提下，使自己的满意度达到最大。 满意度是指所购买的每件物品的价格与重要度的乘积的之和，具体地说，记第 件物品的价格为 ，重要度为 ；现在，一共选中了 件物品，编号依次为 ，则满意度计算为： 请你帮助王强计算可获得的最大的满意度。

输入描述:

第一行输入两个整数 代表预算、需要购买的物品总数。此后 行，第 行输入三个整数 代表第 件物品的价格、重要度、主件编号。特别地， 代表该物品为主件。编号即输入顺序，从 开始。特别地，保证全部物品的价格 均为 的倍数。

输出描述:

在一行上输出一个整数，代表王强可获得的最大满意度。