Elevator

Time limit1sMemory limit128 MB

Summary

Given three step sizes and a reset-to-1 button, count how many floors from 1 to h an elevator starting at floor 1 can reach.

Level: Medium6 of 10
Topics: BFS, Math, Number theory
Solved: No attempts yet

Problem

Donghyeok got a job at a company that builds the only elevator of its kind in the world. The moment he joined, he was put in charge of designing a new elevator for a building with $h$ floors.

After several sleepless nights, Donghyeok came up with an elevator that has only 4 buttons. Each button works as follows:

Go up $a$ floors from the current floor.
Go up $b$ floors from the current floor.
Go up $c$ floors from the current floor.
Return immediately to floor 1.

The elevator starts on floor 1. A passenger presses these buttons in any order, as many times as they wish, to reach a target floor. However, if pressing one of the "go up" buttons would move the elevator above floor $h$ (the top floor of the building), the elevator does not move.

To prove that his design is worthwhile, Donghyeok wants to count how many distinct floors this elevator can reach. (Floor 1, where the elevator starts, counts as reachable.)

Input

The first line contains the height of the building $h$ . ( $1 \le h \le 10^{18}$ )

The second line contains three integers $a$ , $b$ , $c$ separated by spaces. ( $1 \le a, b, c \le 100{,}000$ )

Output

Print the number of distinct floors the elevator can reach.

Examples3

Example 1
Input
```
15
4 7 9
```
Expected output
```
9
```
Example 2
Input
```
1
2 3 5
```
Expected output
```
1
```
Example 3
Input
```
10
2 3 5
```
Expected output
```
9
```