Baked Goods

You have purchased a new oven that has infinite storage space and can be set to a given temperature instantly, meaning you can now create baked goods at a faster rate than ever before!

Unfortunately, different recipes call for different temperatures for the goods to be baked at.

As you want to save time, you are willing to bake an item in the oven if the difference in temperature between the oven and the correct temperature to bake the item at is no greater than ~5~ degrees.

Given a list of items to bake, what is the shortest amount of time needed to bake all items?

Input

The first line consists of an integer ~t~ ~(1 \leq t \leq 1000)~, the number of items that you want to bake.

Each test case will contain 2 integers in the form of ~H~ ~T~ ~(1 \leq H, T \leq 1000)~, representing the temperature the item should be baked at and how many minutes it should be baked for.

Output

For each test case, print the fewest amount of minutes needed to bake all the items.

Example

Input

3
160 20
165 40
175 35

Output

55

The oven can first be set at 160, meaning the first and second can be baked simultaneously. After 20 minutes, the first is done. Set the oven to 170 degrees, meaning the second and third can be baked simultaneously. After 20 minutes, the second is done. After 15 more minutes, the third is done.

The total amount of time is 20 + 20 + 15 = 55 minutes.