Background

zoey学姐最近迷上了植物大战僵尸

Description

今年是植物大战僵尸发行的12周年，他们举行了战斗之夜活动（僵尸告诉你这是真的）。你需要做的是在有限的阳光数内选择更多威力大的植物，来达成最大威力以欢迎僵尸们的拜访。

Format

Input

首先输入一个阳光总数，随后n行输入每一种植物的需要的阳光值、产生的威力和该植物最大购买数。

Output

输出一个整数最大威力值 1<=植物种类数n<=100

0<=阳光总数<=10000

1<=每种植物需要的阳光值<=100

1<=每种植物产生的威力<=1000

1<=每种植物最大购买数<=1000

Samples

100 3
20 3 2
40 1 1
30 8 2

22

Limitation

1s, 1024KiB for each test case.