Alice sống trong một toà chung cư cao ~N~ tầng, các tầng được đánh số từ ~1~ đến ~N~. Để thuận tiện việc đi lại giữa các tầng, toà chung cư lắp đặt một thang máy. Giả sử tầng hiện tại của thang máy là ~F~. Thang máy có ~4~ nút bấm tương ứng với những hành động sau:

• Về tầng ~1~.
• Lên thêm ~a~ tầng, nếu ~F + a \le N~.
• Lên thêm ~b~ tầng, nếu ~F + b \le N~.
• Lên thêm ~c~ tầng, nếu ~F + c \le N~.

Là một kiến trúc sư thiên tài, Alice nhận thấy rằng sẽ có một số tầng mà thang máy không thể đến được, nhưng vì số tầng quá lớn nên không thể đếm hết. Giả sử thang máy đang ở tầng ~1~, hãy giúp Alice tính số tầng của toà chung cư có thể đi đến được từ tầng ~1~ nhé.

Input

Dòng đầu chứa số nguyên ~N~ (~1 \le N \le 10^{18}~).

Dòng thứ hai chứa ba số nguyên ~a~, ~b~, ~c~ (~1 \le a, b, c \le 10^5~).

Output

In ra một số nguyên là số tầng của toà chung cư có thể đi đến được từ tầng ~1~.

Scoring

• Subtask 1 (~40\%~ số điểm): ~N \le 1003973~.
• Subtask 2 (~60\%~ số điểm): Không có ràng buộc gì thêm.

Example

Input:

10
2 6 9

Output

6