Assigning rooms

Every sixth-grade girl at Jeongbo Elementary School is going on a three-day school trip. The lodge has three kinds of rooms, each kind with a different capacity (the number of beds in the room), and as many rooms of each kind as needed. The school wants to split the students among rooms so that no assigned room has an empty bed.

For example, if the rooms hold 5, 9 and 12 people and there are 113 students, booking four 5-person rooms, five 9-person rooms and four 12-person rooms leaves no empty bed. Using ten 5-person rooms and seven 9-person rooms, with no 12-person room at all, also works. If instead the rooms hold 3, 6 and 9 people and there are 112 students, no assignment without an empty bed exists.

Given three distinct positive integers for the room capacities and one positive integer for the number of students, write a program that decides whether the students can be assigned with no empty bed. As in the example above, you may use only one kind or two kinds of room instead of all three.

The first line contains three distinct positive integers $A$, $B$, $C$ ($1 \le A < B < C \le 50$) for the room capacities and a positive integer $N$ ($1 \le N \le 300$) for the number of students, separated by spaces.

Print 1 if the students can be assigned with no empty bed, and 0 otherwise.