In Karaoke, you are usually given a fixed amount of time to sing songs you like (e.g. 3 hours) and you can choose any songs that are available via the karaoke screen. Once time runs out, the screen will be automatically locked such that you can still finish your current song, but you would not be able to select any more songs nor proceed to the next songs.
In order to "extend" the singing time, people will usually choose the longest song available right before the screen is locked out so that they can still sing for the longest time after the screen is locked. In a popular karaoke chain, this song happened to be 勁歌金曲2 (For the sake of this task, let's call it "Golden Songs") by Leo Ku. The KTV of this song is 12 minutes and 48 seconds (or 768 seconds) long while a typical song is only about 3-5 minutes long. Therefore, if you pick Golden Songs as your last song right the screen is locked, instead of other songs, you would typically get to sing for at least an additional 7 minutes. Therefore, as a smart customer singing often in Karaoke, you look to maximize your singing time.
Formally, you have $$$T$$$ seconds of singing time remaining ($$$1 \le T \le 18,000$$$). The screen will be automatically locked at the $$$T$$$-th second, meaning that the latest time to start a new song would be the $$$T-1$$$ second. In addition to Golden Songs, you will have an additional 3 songs that you can choose before the screen is locked. The three songs will be $$$A$$$, $$$B$$$, and $$$C$$$ seconds long respectively ($$$180 \le A, B, C \le 300$$$). ALL songs can be played an unlimited number of times (as long as the screen is not locked) but must be played in full (i.e. it is not possible to play only part of the songs). For the sake of this task, assume that it will take no time to switch to the next song and there are currently no songs playing. Because you are too excited to sing, you would not leave any idle time in the karaoke (i.e. you must be playing a song at all times). Your task is to find out the maximum singing time possible.
The only line contains four integers $$$T$$$, $$$A$$$, $$$B$$$, and $$$C$$$.
$$$1 \le T \le 18,000$$$
$$$180 \le A, B, C \le 300$$$
Output a single integer – the maximum singing time possible in seconds.
601 180 210 300
1368
3 200 190 180
768
In the first example, you should play the 3 additional songs (e.g. the first song once and the second song twice / the third songs twice) for a total of 600 seconds of singing time. 1 second before the screen locks, play Golden Songs for 768 seconds to achieve a total singing time of 1368 seconds.
In the second example, because there is not enough time left, the best strategy would be to play Golden songs right from the beginning for a total singing time of 768 seconds.
