A factory numbers its production batches sequentially starting from 1. Two independent certification tracks inspect finished batches: Track A and Track B. Track A refuses to certify any batch number that is a multiple of d1 (those numbers are reserved for scheduled maintenance), and Track B refuses to certify any batch number that is a multiple of d2. A batch number may be claimed by at most one track — never both — and a track never needs to claim every batch number, only enough of them.
Track A must claim at least c1 batch numbers, and Track B must claim at least c2 batch numbers, with all claims coming from batch numbers 1 through some ceiling N (batch numbers above N have not been produced yet). Find the smallest possible N for which such a claim assignment exists.
A single line with four integers: d1 d2 c1 c2.
A single integer: the minimum ceiling N.
Example 1
Input
2 7 1 1
Expected
2
Explanation
With N = 2, the batch numbers available are {1, 2}. Track A (rejects multiples of 2) can claim {1}, and Track B (rejects multiples of 7) can claim {2}, disjoint from Track A's claim. Both quotas of 1 are met, and N = 1 cannot work because only one batch number would exist total while two disjoint claims are needed, so the answer is 2.
Example 2
Input
2 2 1 1
Expected
3
Explanation
Both tracks reject multiples of 2, so only odd batch numbers can be claimed by either track, and each odd number can go to at most one of them. With N = 2 there is only one odd number (1), not enough to supply two disjoint claims. With N = 3 the odd numbers are {1, 3}: Track A claims {1} and Track B claims {3} (batch 2 stays unclaimed), meeting both quotas, so the answer is 3.
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 →