Coco Fănel (a famous space pirate) and his crew struggled for years to find the ingredients of the Pirate's Shawarma (a food that is said to give godly powers to whoever eats a part of it), and they finally managed to get all of them yesterday. After that, they made the Shawarma and threw a party to celebrate their lifelong goal being achieved. However, a spy of the Absolute Empire, the cruelest empire of all time, managed to steal the Shawarma and is heading towards Absolute's capital city to take this godly food to his emperor. Coco Fănel found this after the party and is gathering strength to get to the capital city, knowing that the emperor is away and won't be able to eat the Shawarma as soon as it arrives in the capital city. To be sure that he will make it on time, he wants to arrive at his destination in the minimum number of days possible.

On the way to the capital city, there are ~N~ ships of the Absolute's Empire scattered around that will try to stop Coco Fănel, so each time Coco meets an enemy ship, a battle will start. Coco must win each fight in order to advance to the capital city, and each fight will take a day. Each ship has three stats (armor, attack and speed), and each battle will be turn-based, described as follows:

On each turn, the ship with the higher speed of the two battling will attack first, then the other one's attack will follow (if they have equal speed, Coco Fanel attacks first). An attack of a ship with the attack stat ~A~ will destroy ~A~ points of armor of the attacked ship. Immediately after a ship is directly hit by an attack (the armor of the ship will be lower than ~0~), that ship loses the battle and retreats. After each fight, each ship's armor is automatically fully repaired.

Before battling any ship, Coco Fănel must strengthen his ship since his ship's stats are all initially ~0~. For each point he wants to invest in a stat, he must spend a day upgrading his ship. Given ~N~ and the stats of each enemy ship, output the number of days Coco must spend to get to the capital of the Absolute Empire.

Constraints

Subtask 1 [20%]

• ~1 \le N \le 1\,000~
• ~1 \le speed, attack, armor \le 1\,000~

Subtask 2 [80%]

• ~1 \le N \le 100\,000~
• ~1 \le speed, attack, armor \le 100\,000~

Input Specification

On the first line, you will find ~N~.
On the next ~N~ lines, you will find the ships' stats. On the ~i~-th line you will have ~speed[i]~, ~attack[i]~ and ~armor[i]~.

Output Specification

On the first line, you will print the minimum number of required days until Coco Fănel has a ship that beats all the other ships.

Sample Input 1

2
5 1 20
5 2 20

Sample Output 1

13

Explanation for Sample Output 1

An airship with ~0~ speed, ~7~ attack and ~6~ armor will be able to defeat all of the given ships.

Sample Input 2

2
6 1 5
6 10 4

Sample Output 2

12

Sample Input 3

2
5 6 1
6 2 5

Sample Output 3

8