방 배정하기

정보 초등학교 6학년 여학생 전원이 2박 3일 수학여행을 간다. 학생들이 묵을 숙소에는 정원(방 안의 침대 수)이 서로 다른 세 종류의 방이 있고, 같은 종류의 방은 필요한 만큼 얼마든지 쓸 수 있다. 학교는 배정한 모든 방에 빈 침대가 하나도 남지 않도록 학생을 나누어 넣으려 한다.

예를 들어 방의 종류가 5인실, 9인실, 12인실이고 학생이 113명이면 5인실 4개, 9인실 5개, 12인실 4개를 예약해 빈 침대 없이 배정할 수 있다. 12인실을 쓰지 않고 5인실 10개와 9인실 7개만 쓰는 배정도 가능하다. 반면 방의 종류가 3인실, 6인실, 9인실이고 학생이 112명이면 빈 침대 없는 배정은 불가능하다.

방의 정원을 나타내는 서로 다른 세 자연수와 전체 학생 수가 주어질 때, 빈 침대 없이 방을 배정할 수 있는지 판정하는 프로그램을 작성하시오. 위 예에서처럼 세 종류를 모두 쓰지 않고 한 종류나 두 종류만 써도 된다.

첫째 줄에 방의 정원을 나타내는 서로 다른 세 자연수 $A$, $B$, $C$ ($1 \le A < B < C \le 50$)와 전체 학생 수를 나타내는 자연수 $N$ ($1 \le N \le 300$)이 공백으로 구분되어 주어진다.

빈 침대 없이 배정할 수 있으면 1을, 불가능하면 0을 출력한다.