Background

Special for beginners, ^_^

Description

奶牛们准备升空了！为了进入轨道，他们计划建造一座由各种材料堆成的巨型太空电梯。她们拥有 K (1 ≤ K ≤ 400)种型号不同的材料，i型材料的单位长度为hi (1 ≤ hi≤ 100)，数量为 ci (1 ≤ ci≤ 10)，由于宇宙射线可能危及材料安全，因此规定堆建材料时，每块 i型材料的高度都不能超过 ai (1 ≤ ai≤ 40000)。 请帮助奶牛们用这些材料堆出尽可能高的太空电梯。

Format

Input

第一行：一个整数 K，第二行到第 K + 1 行：每行三个整数：hi，ai，ci。第 i + 1 行描述的是第 i 块材料的性质

Output

第一行：一个整数 H，表示电梯的最高高度

Samples

3
7 40 3
5 23 8
2 52 6

48

Limitation

1s, 1024KiB for each test case.