Maximum Height With Return to Start

You are given integers days, up and down. You start at height 0 and make one move per day for days days.

Each move either goes up by any whole amount from 0 to up, or goes down by any whole amount from 0 to down. After the last day you must be back at height 0.

Return the greatest height you can reach while still ending back at height 0.

If days is 1, the only plan that ends at height 0 is to not move, so the answer is 0.

Examples

Example 1

Input: days = 3, up = 4, down = 3
Output: 4
Explanation: Go up 4 (height 4), down 3 (height 1), then down 1 (height 0). Height 5 would take 2 days going up (at most 4 per day) and 2 days going down (at most 3 per day), which is 4 days.

Example 2

Input: days = 2, up = 5, down = 5
Output: 5
Explanation: Go up 5 on the first day and down 5 on the second.

Example 3

Input: days = 4, up = 6, down = 5
Output: 10
Explanation: Go up 6 (height 6), up 4 (height 10), down 5 (height 5), then down 5 (height 0). Height 11 would take 2 days going up and 3 days going down, which is 5 days.

Example 4

Input: days = 1, up = 7, down = 7
Output: 0
Explanation: Any move on the only day leaves you away from height 0, so you must not move.