Let a(n,k) be the cost of n brooms using k factories. S(k, i) the cost of i brooms produced in k-th factory. Then

a(n,k) = { min i from 0 to min n of { a(n-i,k-1) + S(k,i) }, if Kk >= n }
         { 4200000000, otherwise                                            }
Kk - maximal amount of brooms that could be produced in k-th factory.