In order to forge k weapons,

we would need -> k*a-(k-1)*b = a + (k-1)*(a-b).

This should be less than cj (ingots of metal j). a + (k-1)*(a-b)<=cj So k <= 1 + (cj-a)/(a-b).

We can simply take the highest k = 1 + floor((cj-a)/(a-b)).

Its always optimal to melt a tool after forging (gives x experience and bi additional units of that metal).

Now, if we forge ith tool k times using metal j, we would use — ai+(ai-bi)+(ai-bi)...-bi = k(ai-bi) units of metal j

(the last minus comes when we melt after last forging) __

So for each metal, we can start forging in the increasing order of (ai-bi). Still figuring out how to bring this down from O(n*m) :(

https://cp-algorithms.com/string/string-hashing.html

Thanks! Found it to be more intuitive than the posted solution