시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 29 2 2 50.000%

문제

동혁이는 엘리베이터를 만드는 회사에 취직했다. 이 회사는 세상에서 오직 하나뿐인 엘리베이터를 만든다.

동혁이는 입사하자마자 h층 건물에 들어갈 새로운 엘리베이터를 만드는 프로젝트에 투입되었다. 다가오는 회의에서 동혁이는 기존에 없던 새로운 엘리베이터를 생각해서 제안서를 제출해야 한다.

몇 일동안 밤샘 끝에 동혁이는 버튼 4개만 가지고 있는 엘리베이터를 생각해냈다. 버튼은 다음과 같은 기능을 갖는다.

  1. a층 올라가는 버튼
  2. b층 올라가는 버튼
  3. c층 올라가는 버튼
  4. 1층으로 되돌아오는 버튼

처음에 엘리베이터는 1층에 있다. 탑승객은 이 세 버튼을 이용해서 자기가 올라가야하는 층까지 올라가야 한다. 만약, a, b, c층 위에 해당하는 층이 없을 때는(h층 위) 엘리베이터는 움직이지 않는다.

동혁이는 자신의 제안이 가치가 있다는 것을 증명하기 위해서, 이 엘리베이터로 올라갈 수 있는 층의 개수를 세려고 한다.

입력

첫째 줄에 빌딩의 높이 h가 주어진다. (1 ≤ h ≤ 1018)

둘째 줄에 a, b, c가 주어진다. (1 ≤ a,b,c ≤ 100,000)

출력

동혁이가 제안한 엘리베이터를 가지고 이동할 수있는 층의 수를 출력한다.

예제 입력 1

15
4 7 9

예제 출력 1

9
W3sicHJvYmxlbV9pZCI6IjM1OTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1ZDhcdWI5YWNcdWJjYTBcdWM3NzRcdWQxMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWM1ZDhcdWI5YWNcdWJjYTBcdWM3NzRcdWQxMzBcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0IFx1ZDY4Y1x1YzBhY1x1YzVkMCBcdWNkZThcdWM5YzFcdWQ1ODhcdWIyZTQuIFx1Yzc3NCBcdWQ2OGNcdWMwYWNcdWIyOTQgXHVjMTM4XHVjMGMxXHVjNWQwXHVjMTFjIFx1YzYyNFx1YzljMSBcdWQ1NThcdWIwOThcdWJmZDBcdWM3NzggXHVjNWQ4XHViOWFjXHViY2EwXHVjNzc0XHVkMTMwXHViOTdjIFx1YjljY1x1YjRlMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViM2Q5XHVkNjAxXHVjNzc0XHViMjk0IFx1Yzc4NVx1YzBhY1x1ZDU1OFx1Yzc5MFx1YjljOFx1Yzc5MCBoXHVjZTM1IFx1YWM3NFx1YmIzY1x1YzVkMCBcdWI0ZTRcdWM1YjRcdWFjMDggXHVjMGM4XHViODVjXHVjNmI0IFx1YzVkOFx1YjlhY1x1YmNhMFx1Yzc3NFx1ZDEzMFx1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVkNTA0XHViODVjXHVjODFkXHVkMmI4XHVjNWQwIFx1ZDIyY1x1Yzc4NVx1YjQxOFx1YzVjOFx1YjJlNC4gXHViMmU0XHVhYzAwXHVjNjI0XHViMjk0IFx1ZDY4Y1x1Yzc1OFx1YzVkMFx1YzExYyBcdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgXHVhZTMwXHVjODc0XHVjNWQwIFx1YzVjNlx1YjM1OCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVjNWQ4XHViOWFjXHViY2EwXHVjNzc0XHVkMTMwXHViOTdjIFx1YzBkZFx1YWMwMVx1ZDU3NFx1YzExYyBcdWM4MWNcdWM1NDhcdWMxMWNcdWI5N2MgXHVjODFjXHVjZDljXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYTg3IFx1Yzc3Y1x1YjNkOVx1YzU0OCBcdWJjMjRcdWMwZDggXHViMDVkXHVjNWQwIFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWJjODRcdWQyYmMgNFx1YWMxY1x1YjljYyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YzVkOFx1YjlhY1x1YmNhMFx1Yzc3NFx1ZDEzMFx1Yjk3YyBcdWMwZGRcdWFjMDFcdWQ1NzRcdWIwYzhcdWIyZTQuIFx1YmM4NFx1ZDJiY1x1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWUzMFx1YjJhNVx1Yzc0NCBcdWFjMTZcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+YVx1Y2UzNSBcdWM2MmNcdWI3N2NcdWFjMDBcdWIyOTQgXHViYzg0XHVkMmJjPFwvbGk+XHJcblx0PGxpPmJcdWNlMzUgXHVjNjJjXHViNzdjXHVhYzAwXHViMjk0IFx1YmM4NFx1ZDJiYzxcL2xpPlxyXG5cdDxsaT5jXHVjZTM1IFx1YzYyY1x1Yjc3Y1x1YWMwMFx1YjI5NCBcdWJjODRcdWQyYmM8XC9saT5cclxuXHQ8bGk+MVx1Y2UzNVx1YzczY1x1Yjg1YyBcdWI0MThcdWIzY2NcdWM1NDRcdWM2MjRcdWIyOTQgXHViYzg0XHVkMmJjPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVjYzk4XHVjNzRjXHVjNWQwIFx1YzVkOFx1YjlhY1x1YmNhMFx1Yzc3NFx1ZDEzMFx1YjI5NCAxXHVjZTM1XHVjNWQwIFx1Yzc4OFx1YjJlNC4gXHVkMGQxXHVjMmI5XHVhYzFkXHVjNzQwIFx1Yzc3NCBcdWMxMzggXHViYzg0XHVkMmJjXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWM3OTBcdWFlMzBcdWFjMDAgXHVjNjJjXHViNzdjXHVhYzAwXHVjNTdjXHVkNTU4XHViMjk0IFx1Y2UzNVx1YWU0Y1x1YzljMCBcdWM2MmNcdWI3N2NcdWFjMDBcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIGEsIGIsIGNcdWNlMzUgXHVjNzA0XHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWNlMzVcdWM3NzQgXHVjNWM2XHVjNzQ0IFx1YjU0Y1x1YjI5NChoXHVjZTM1IFx1YzcwNCkgXHVjNWQ4XHViOWFjXHViY2EwXHVjNzc0XHVkMTMwXHViMjk0IFx1YzZjMFx1YzljMVx1Yzc3NFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjODFjXHVjNTQ4XHVjNzc0IFx1YWMwMFx1Y2U1OFx1YWMwMCBcdWM3ODhcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzk5ZFx1YmE4NVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMsIFx1Yzc3NCBcdWM1ZDhcdWI5YWNcdWJjYTBcdWM3NzRcdWQxMzBcdWI4NWMgXHVjNjJjXHViNzdjXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZTM1XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWMxMzhcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJlNGNcdWI1MjlcdWM3NTggXHViMTkyXHVjNzc0IGhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IGggJmxlOyAxMDxzdXA+MTg8XC9zdXA+KTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwIGEsIGIsIGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IGEsYixjICZsZTsgMTAwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWIzZDlcdWQ2MDFcdWM3NzRcdWFjMDAgXHVjODFjXHVjNTQ4XHVkNTVjIFx1YzVkOFx1YjlhY1x1YmNhMFx1Yzc3NFx1ZDEzMFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOFx1Yzc4OFx1YjI5NCBcdWNlMzVcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNTk4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRWxldmF0b3IiLCJkZXNjcmlwdGlvbiI6IjxwPkVkd2FyZCB3b3JrcyBhcyBhbiBlbmdpbmVlciBmb3IgTm9uLXRyaXZpYWwgRWxldmF0b3JzOiBFbmdpbmVlcmluZywgUmVzZWFyY2ggYW5kIENvbnN0cnVjdGlvbiAoTkVFUkMpLiBIaXMgbmV3IHRhc2sgaXMgdG8gZGVzaWduIGEgYnJhbmQgbmV3IGVsZXZhdG9yIGZvciBhIHNreXNjcmFwZXIgd2l0aCBoIGZsb29ycy48XC9wPlxyXG5cclxuPHA+RWR3YXJkIGhhcyBhbiBpZCZhY3V0ZTtlZSBcdWZiMDF4ZTogaGUgdGhpbmtzIHRoYXQgZm91ciBidXR0b25zIGFyZSBlbm91Z2ggdG8gY29udHJvbCB0aGUgbW92ZW1lbnQgb2YgdGhlIGVsZXZhdG9yLiBIaXMgbGFzdCBwcm9wb3NhbCBzdWdnZXN0cyB0aGUgZm9sbG93aW5nIGZvdXIgYnV0dG9uczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5Nb3ZlIGEgZmxvb3JzIHVwLjxcL2xpPlxyXG5cdDxsaT5Nb3ZlIGIgZmxvb3JzIHVwLjxcL2xpPlxyXG5cdDxsaT5Nb3ZlIGMgZmxvb3JzIHVwLjxcL2xpPlxyXG5cdDxsaT5SZXR1cm4gdG8gdGhlIFx1ZmIwMXJzdCBmbG9vci48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Jbml0aWFsbHksIHRoZSBlbGV2YXRvciBpcyBvbiB0aGUgXHVmYjAxcnN0IGZsb29yLiBBIHBhc3NlbmdlciB1c2VzIHRoZSBcdWZiMDFyc3QgdGhyZWUgYnV0dG9ucyB0byByZWFjaCB0aGUgZmxvb3Igc2hlIG5lZWRzLiBJZiBhIHBhc3NlbmdlciB0cmllcyB0byBtb3ZlIGEsIGIgb3IgYyBmbG9vcnMgdXAgYW5kIHRoZXJlIGlzIG5vIHN1Y2ggZmxvb3IgKHNoZSBhdHRlbXB0cyB0byBtb3ZlIGhpZ2hlciB0aGFuIHRoZSBoLXRoIGZsb29yKSwgdGhlIGVsZXZhdG9yIGRvZXNuJnJzcXVvO3QgbW92ZS48XC9wPlxyXG5cclxuPHA+VG8gcHJvdmUgaGlzIHBsYW4gd29ydGh5LCBFZHdhcmQgd2FudHMgdG8ga25vdyBob3cgbWFueSBmbG9vcnMgYXJlIGFjdHVhbGx5IGFjY2Vzc2libGUgZnJvbSB0aGUgZmxyc3QgZmxvb3IgdmlhIGhpcyBlbGV2YXRvci4gSGVscCBoaW0gY2FsY3VsYXRlIHRoaXMgbnVtYmVyLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGZpbGUgY29udGFpbnMgb25lIGludGVnZXIgaCAmbWRhc2g7IHRoZSBoZWlnaHQgb2YgdGhlIHNreXNjcmFwZXIgKDEgJmxlOyBoICZsZTsgMTA8c3VwPjE4PFwvc3VwPik8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIHRocmVlIGludGVnZXJzIGEsIGIgYW5kIGMgJm1kYXNoOyB0aGUgcGFyYW1ldGVycyBvZiB0aGUgYnV0dG9ucyAoMSAmbGU7IGEsYixjICZsZTsgMTAwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgb25lIGludGVnZXIgbnVtYmVyICZtZGFzaDsgdGhlIG51bWJlciBvZiBmbG9vcnMgdGhhdCBhcmUgcmVhY2hhYmxlIGZyb20gdGhlIGZpcnN0IGZsb29yLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==