
99  ZOJ Monthly, November 2010  H
Hiiragi likes collecting sticks. It is said that she has collected m short sticks. One day, she was very excited that she found more sticks from a box under her bed. These new sticks have n different lengths, while for each length, there are infinite sticks of the same length.
Hiiragi then came up with an idea, that concatenates the new sticks in different
ways to form long sticks of all possible lengths no longer than L.
Let's name the lengths a set S. Her mother told her that "Use each of
your m short sticks to measure each of the lengths in S. When
you find a short sticks being able to measure a length in integer times, get
the times it takes and denote it as t. I will give you one candy if you
can find one way that uses the following rules to reduce t to 1."
So here, you are required to calculate how many candies Hiiragi can get at most.
Input
The first line is T ( ≤ 10), the number of test cases. OutputFor each case, print one integer, the number of candies Hiiragi can get at most. Sample Input1 2 4 12 4 6 1 3 4 3 Sample Output16 Hint
In the sample, using sticks of length 4 and 6 can make long sticks of
S = {4, 6, 8, 10, 12}. Author: ZHUANG, Junyuan Contest: ZOJ Monthly, November 2010 