|Online Judge||Problem Set||Authors||Online Contests||User|
Facer is the chemical keeper in a laboratory. Every day he receives M requests of a certain kind of chemical which is vital to a large variety of experiments. The ith request asks for Ri grams of the chemical and Facer has to weigh the chemicals in the exact order as the requests listed or he will mess up all the experiments.
The balance used in the laboratory has N different kinds of poises. The ith kind weighs Wi grams. The amount of poises of each kind is so large that can be considered as infinite. The poises are all in a flat shape. When Facer wants to weigh the chemical, he has to stack the poises on the left side of the balance one by one in such a way that the lighter ones are always above the heavier ones. For example, a 2-gram poise is never allowed to be on the top of a 1-gram poise.
To accelerate his work, Facer tries to use the minimum steps to finish the weighing. For each step he can put one poise on the top of the stack (as long as no poises in the stack is lighter than it) or remove the poise which is currently on the top.
The first line of the input contains the number of the test cases.
For each test case, output a line containing the minimum number of steps Facer needed to finish all the requests. If any request can not be weighed out, output -1 instead.
2 3 1 2 3 3 4 5 6 2 3 4 3 1 6 8
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator