URI Online Judge | 2076

Great Allocation of Commodities

By XII Maratona de Programação IME-USP, 2008 BR Brazil

Timelimit: 1

Tjalling C. Koopmans won the Nobel Prize in economy in 1975 with the Russian mathematic Kantorovich for their contributions in important areas like the great allocation of resources. Koopmans was graduated in mathematic for the university of Utrcht, in Netherland, and specialized himself in mathematic economy. Throughout the Second World War he was involved in the study of the great allocation of resources, which 30 years later gave him the Nobel Prize. He is considering one of the pioneers in the linear theory program. His contribution has important applications in economy, mathematic, physics and in chemistry.

One of Koopmans' favorite problems were the great allocation of commodities. In this problem, is given an initial value and a final value of the application to be done. Although, not all the values can be applied in several investments. Each investment is defined through the integer number, and for convention, can be applied only when the value to be applied is a multiple at least of one number that defines an investment.

Your work in this problem is calculating the maximum value that can be applied. So, given the list of integer that defines the multiple applications and the initial value and in the final value to be applied, you may calculate the sum of the values that can be applied in the interval.


The input is composed of several instances. The first input line contains an integer T indicating the number of instances.

The first line of each instance has three integers I, F and N (1 < I < F < 1000000000 and 1 < N < 20) that represents the initial value, final value and the number of the elements in the application list. The next line contains N integers 1 < ai < 10000000000 indicating the list of applications.


For each instance print a line containing the sum of values that can be apply in the break. This value can be too big so print the model result 1300031.

Sample Input Sample Output

1 10 1
1 9 2
1 999 2