utils/scrapers/prescraped/codeforces/Problems/1989D

You are playing a famous computer game (that just works) where you have various skills you can level up. Today, you focused on the "Smithing" skill. Your tactic is obvious: forging weapons from ingots and then melting them back to return the materials partially. For simplicity, every time you create an item, you get 1 experience point, and every time you melt an item, you also get 1 experience point.There are n classes of weapons you can forge and m types of metal ingots.You can create one weapon of the i-th class, spending ai ingots of metal of the same type. Melting a weapon of the i-th class (which you crafted earlier) returns you bi ingots of the type of metal it was made of.You have cj metal ingots of the j-th type, and you know that you can craft a weapon of any class from any metal type. Each combination of a weapon class and a metal type can be used any number of times.What is the maximum total amount of experience you can earn by crafting and melting weapons?