Problem

Pancake Deque solution codejam

The lines at the air pump at your gas station are getting too long! You want to optimize the process to help customers more quickly inflate their tires, sports balls, giant parade balloon animals, and other products.

The pump is automatic: you set the pressure to a specific number of pascals and plug the pump into the inflatable product, and it will inflate as needed to that exact pressure. There are only two buttons on the pump: up and down. They increase and decrease the target pressure, respectively, by exactly 11 pascal.

There is a line of NN customers, each of whom brings exactly PP products that they need to get inflated by the pump. You know the target pressure of each product. You can inflate the products from a customer in any order you want, but you cannot change the order of the customers. Specifically, you must inflate all products from the ii⁠-th customer before inflating any from the (i+1)(i+1)⁠-th customer. In between handling two products, if those two products have different target pressures, you need to use the buttons on the pump.

The pump is initially set to  pascals, and it can be left at any number after all products of all customers have been inflated. If you order the products of each customer optimally, what is the minimum number of button presses you need?

Input

Pancake Deque solution codejam

The first line of the input gives the number of test cases, TT. TT test cases follow. Each test case starts with a line containing two integers, NN and PP: the number of customers and the number of products each customer brings, respectively. Then, NN lines follow. The ii-th of these lines contains PP integers Xi,1,Xi,2,…,Xi,PXi,1,Xi,2,…,Xi,P, representing that the jj-th product that the ii-th customer brings has a target pressure of Xi,jXi,j pascals.

Output

For each test case, output one line containing Case #xx: yy, where xx is the test case number (starting from 1) and yy is the minimum number of button presses needed to inflate all products according to their specified pressures.

Limits

Time limit: 5 seconds.
Memory limit: 1 GB.
1≤T≤1001≤T≤100.
1≤Xi,j≤1091≤Xi,j≤109, for all i,ji,j.

Test Set 1 (Visible Verdict)

2≤N≤102≤N≤10.
2≤P≤32≤P≤3.

Test Set 2 (Hidden Verdict)

Pancake Deque solution codejam

2≤N≤10002≤N≤1000.
2≤P≤1002≤P≤100.

Sample

2
3 3
30 10 40
20 50 60
60 60 50
5 2
1 1000000000
500000000 1000000000
1 1000000000
500000000 1
1 1000000000

Case #1: 110
Case #2: 4999999996

In Sample Case #1, an optimal way to use the pump is:

1. press up 1010 times, setting the pump to 1010; pump the product (from customer 1) that needs 1010 pascals,
2. press up 3030 times, setting the pump to 4040; pump the product (from customer 1) that needs 4040 pascals,
3. press down 1010 times, setting the pump to 3030; pump the product (from customer 1) that needs 3030 pascals,
4. press down 1010 times, setting the pump to 2020; pump the product (from customer 2) that needs 2020 pascals,
5. press up 3030 times, setting the pump to 5050; pump the product (from customer 2) that needs 5050 pascals,
6. press up 1010 times, setting the pump to 6060; pump the product (from customer 2) and the two products (from customer 3) that need 6060 pascals, and finally
7. press down 1010 times, setting the pump to 5050; pump the product (from customer 3) that needs 5050 pascals.

This is a total of $$$110$$ button presses.

In Sample Case #2, notice that the answer can be larger than 232232.

Admin

I am the Founder and the creator of the blog neoideasblog.com where we share latest trivia questions and answers on a daily basis.