Pearls

Interview

Time limit1sMemory limit128 MB

Summary

Given demand and price per pearl for classes in increasing quality order, find the cheapest way to buy all pearls when each class's order may be upgraded to a higher class, paying 10 extra pearls' worth per purchase.

Level: Medium5 of 10
Topics: Dynamic programming, Prefix sum, Implementation
Solved: No attempts yet

Problem

In Pearlania, everybody is fond of pearls. A company called The Royal Pearl produces a great deal of pearl jewelry. It delivers to the royal family, but it also makes bracelets and necklaces for ordinary people, using pearls of much lower quality.

Pearls are separated into 100 quality classes. Each class is identified by the price of a single pearl in that class; this price is unique to the class. A higher-quality class always costs more per pearl than a lower one.

Every month the stock manager prepares a list of how many pearls are needed in each quality class. The pearls are bought on the local pearl market. In addition to the per-pearl price, every completed purchase in a class costs an extra amount equal to the price of ten pearls of that class (this surcharge discourages buying just a single pearl). So buying $a$ pearls in a class whose price is $p$ costs $(a + 10)\times p$ .

To save money, the CFO may buy pearls in a higher quality class than requested, but never in a lower one. Customers do not mind receiving better pearls as long as the price stays the same. Merging several classes into one higher-class purchase can reduce the total surcharge.

For example, suppose 5 pearls are needed in the 10-Euro class and 100 pearls in the 20-Euro class. Buying them separately costs $(5 + 10)\times 10 + (100 + 10)\times 20 = 2350$ Euro. Buying all 105 pearls in the 20-Euro class costs only $(5 + 100 + 10)\times 20 = 2300$ Euro.

Given the number of pearls needed and the price per pearl for several quality classes, compute the lowest possible total price to buy everything on the list. Pearls may be bought in the requested class or in any higher class, but never in a lower one.

Input

The first line contains the number of test cases.

Each test case begins with a line containing the number of quality classes $c$ ( $1 \le c \le 100$ ). Then follow $c$ lines, each with two integers $a_i$ and $p_i$ : the number of pearls $a_i$ needed in that class ( $1 \le a_i \le 1000$ ) and the price per pearl $p_i$ in that class ( $1 \le p_i \le 1000$ ). The classes are listed in ascending order of quality, and therefore of price. All numbers in the input are integers.

Output

For each test case, output a single line containing one integer: the lowest possible total price needed to buy everything on the list.

Examples5

Example 1

Input

Expected output

330
1344

Example 2
Input
```
1
1
1 1
```
Expected output
```
11
```
Example 3
Input
```
1
1
1000 1000
```
Expected output
```
1010000
```
Example 4
Input
```
1
2
1 1
1 1000
```
Expected output
```
11011
```
Example 5
Input
```
1
2
5 10
100 20
```
Expected output
```
2300
```