/**
* March 2013 Long Challenge at Codechef
*
* Problem: LECOINS - Little Elephant and Colored Coins
* Author: Anton Lunyov (Tester)
* Complexity: O(C * N * min(Vi) + C * Q), where C is the number of different colors
* Timing: 1.07 out of 4.00
*
* Description:
* Put m = min(Vi). Let dp[k][x] be the smallest value having residue x modulo m
* for which the maximum number of colors in the representation is k.
* After we find dp[k][x] for all k=0..C and r=0..m-1
* we can answer each query in O(C) time:
* the answer for S is the largest k for which S >= dp[k][S%m]
* since we can add several (maybe zero) coins of value m
* to the representation of dp[k][S%m] to get S.
* Now we need to calculate dp[k][x] for all needed k and x.
* We will process colors one by one and update dp[][] by all coins having current color
* Initially dp[0][0] = 0 while all other dp[k][x] = INF.
* When we process coins of some color we perform two steps:
* 1) We update row dp[k+1] by dp[k] for all k=C..0,
* where C is the number of processed colors before considered one
* Namely for each coin value V we do updMin of dp[k+1][(x+V)%m] by dp[k][x]+V
* This means that adding coin of new color to the representation of dp[k][x].
* It is important to loop k from C to 0
* so that only old values of dp are used for update.
* 2) We update dp[k] by itself for each k.
* Namely for each coin value V we do updMin of dp[k][(x+V)%m] by dp[k][x]+V
* But now we can't do simple loop by x since dp-graph here has cycles.
* One may consider it as the shortest path problem
* and apply some efficient shortest path algorithm like Dijkstra one.
* But this gives us additional log m factor to the complexity.
* In fact, we can do this update in O(m) time.
* For this we note, that dp-graph is a union of non-intersecting simple cycles.
* Hence to do an update we find the minimum dp-value in each cycle
* and do updates starting from it for all vertexes of this cycle.
* The number of cycles is equals to d = gcd(V, m) and the length of each cycle m/d.
*/
#include
#include
#include
#include