A festival garland is wired with n independent ignition modules spaced along its length. Once switched on at time 0, module i fires automatically and instantly at every whole-second multiple of its own firing period p_i — that is, at seconds p_i, 2p_i, 3p_i, and so on — and keeps firing forever at that fixed period. The garland is considered fully ignited as soon as the modules have produced, in total across all of them, at least m firings.
Given the firing periods of all n modules and the required firing count m, find the earliest whole second T at which the garland is fully ignited, i.e., the smallest T such that the combined number of firings that have occurred at times 1, 2, ..., T is at least m.
Line 1: two space-separated integers n and m — the number of ignition modules and the number of firings required to fully ignite the garland. Line 2: n space-separated integers p_1 ... p_n — the firing period, in seconds, of each module.
Print a single integer: the minimum number of whole seconds T after switch-on at which the total firing count across all modules first reaches at least m. The answer may be as large as roughly 10^18, so use a 64-bit (or arbitrary-precision) integer type.
Example 1
Input
2 5 2 3
Expected
6
Explanation
Module 1 (period 2) fires at seconds 2, 4, 6, 8, ...; module 2 (period 3) fires at seconds 3, 6, 9, .... Counting firings in order: by second 2 there is 1 firing, by second 3 there are 2, by second 4 there are 3, and by second 6 module 1's third firing and module 2's second firing both land, bringing the total to 5. At second 5 the total is still only 3 (floor(5/2)+floor(5/3)=2+1=3), so 6 is the earliest second at which the count reaches the required 5.
Example 2
Input
3 1 5 2 9
Expected
2
Explanation
Only one firing is required, so the answer is simply the smallest firing period among the three modules, since that module fires first. Module 2 has period 2, firing at second 2, before the others fire at seconds 5 and 9, so the garland is fully ignited at second 2.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →