시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHViYTcwXHVjZTYwXHViM2Q5XHVjNTQ4IFx1YmMyNFx1YzBkOCBcdWIwNWRcdWM1ZDAgXHViM2Q5XHVkNjAxXHVjNzc0XHViMjk0IFx1YmM4NFx1ZDJiYyA0XHVhYzFjXHViOWNjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjNWQ4XHViOWFjXHViY2EwXHVjNzc0XHVkMTMwXHViOTdjIFx1YzBkZFx1YWMwMVx1ZDU3NFx1YjBjOFx1YjJlNC4gXHViYzg0XHVkMmJjXHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVhZTMwXHViMmE1XHVjNzQ0IFx1YWMxNlx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5hXHVjZTM1IFx1YzYyY1x1Yjc3Y1x1YWMwMFx1YjI5NCBcdWJjODRcdWQyYmM8XC9saT5cclxuXHQ8bGk+Ylx1Y2UzNSBcdWM2MmNcdWI3N2NcdWFjMDBcdWIyOTQgXHViYzg0XHVkMmJjPFwvbGk+XHJcblx0PGxpPmNcdWNlMzUgXHVjNjJjXHViNzdjXHVhYzAwXHViMjk0IFx1YmM4NFx1ZDJiYzxcL2xpPlxyXG5cdDxsaT4xXHVjZTM1XHVjNzNjXHViODVjIFx1YjQxOFx1YjNjY1x1YzU0NFx1YzYyNFx1YjI5NCBcdWJjODRcdWQyYmM8XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWNjOThcdWM3NGNcdWM1ZDAgXHVjNWQ4XHViOWFjXHViY2EwXHVjNzc0XHVkMTMwXHViMjk0IDFcdWNlMzVcdWM1ZDAgXHVjNzg4XHViMmU0LiBcdWQwZDFcdWMyYjlcdWFjMWRcdWM3NDAgXHVjNzc0IFx1YzEzOCBcdWJjODRcdWQyYmNcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1Yzc5MFx1YWUzMFx1YWMwMCBcdWM2MmNcdWI3N2NcdWFjMDBcdWM1N2NcdWQ1NThcdWIyOTQgXHVjZTM1XHVhZTRjXHVjOWMwIFx1YzYyY1x1Yjc3Y1x1YWMwMFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgYSwgYiwgY1x1Y2UzNSBcdWM3MDRcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1Y2UzNVx1Yzc3NCBcdWM1YzZcdWM3NDQgXHViNTRjXHViMjk0KGhcdWNlMzUgXHVjNzA0KSBcdWM1ZDhcdWI5YWNcdWJjYTBcdWM3NzRcdWQxMzBcdWIyOTQgXHVjNmMwXHVjOWMxXHVjNzc0XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViM2Q5XHVkNjAxXHVjNzc0XHViMjk0IFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWM4MWNcdWM1NDhcdWM3NzQgXHVhYzAwXHVjZTU4XHVhYzAwIFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjOTlkXHViYTg1XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYywgXHVjNzc0IFx1YzVkOFx1YjlhY1x1YmNhMFx1Yzc3NFx1ZDEzMFx1Yjg1YyBcdWM2MmNcdWI3N2NcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNlMzVcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YzEzOFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmU0Y1x1YjUyOVx1Yzc1OCBcdWIxOTJcdWM3NzQgaFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgaCAmbGU7IDEwPHN1cD4xODxcL3N1cD4pPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDAgYSwgYiwgY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgYSxiLGMgJmxlOyAxMDAsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YjNkOVx1ZDYwMVx1Yzc3NFx1YWMwMCBcdWM4MWNcdWM1NDhcdWQ1NWMgXHVjNWQ4XHViOWFjXHViY2EwXHVjNzc0XHVkMTMwXHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4XHVjNzg4XHViMjk0IFx1Y2UzNVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM1OTgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJFbGV2YXRvciIsImRlc2NyaXB0aW9uIjoiPHA+RWR3YXJkIHdvcmtzIGFzIGFuIGVuZ2luZWVyIGZvciBOb24tdHJpdmlhbCBFbGV2YXRvcnM6IEVuZ2luZWVyaW5nLCBSZXNlYXJjaCBhbmQgQ29uc3RydWN0aW9uIChORUVSQykuIEhpcyBuZXcgdGFzayBpcyB0byBkZXNpZ24gYSBicmFuZCBuZXcgZWxldmF0b3IgZm9yIGEgc2t5c2NyYXBlciB3aXRoIGggZmxvb3JzLjxcL3A+XHJcblxyXG48cD5FZHdhcmQgaGFzIGFuIGlkJmFjdXRlO2VlIFx1ZmIwMXhlOiBoZSB0aGlua3MgdGhhdCBmb3VyIGJ1dHRvbnMgYXJlIGVub3VnaCB0byBjb250cm9sIHRoZSBtb3ZlbWVudCBvZiB0aGUgZWxldmF0b3IuIEhpcyBsYXN0IHByb3Bvc2FsIHN1Z2dlc3RzIHRoZSBmb2xsb3dpbmcgZm91ciBidXR0b25zOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk1vdmUgYSBmbG9vcnMgdXAuPFwvbGk+XHJcblx0PGxpPk1vdmUgYiBmbG9vcnMgdXAuPFwvbGk+XHJcblx0PGxpPk1vdmUgYyBmbG9vcnMgdXAuPFwvbGk+XHJcblx0PGxpPlJldHVybiB0byB0aGUgXHVmYjAxcnN0IGZsb29yLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkluaXRpYWxseSwgdGhlIGVsZXZhdG9yIGlzIG9uIHRoZSBcdWZiMDFyc3QgZmxvb3IuIEEgcGFzc2VuZ2VyIHVzZXMgdGhlIFx1ZmIwMXJzdCB0aHJlZSBidXR0b25zIHRvIHJlYWNoIHRoZSBmbG9vciBzaGUgbmVlZHMuIElmIGEgcGFzc2VuZ2VyIHRyaWVzIHRvIG1vdmUgYSwgYiBvciBjIGZsb29ycyB1cCBhbmQgdGhlcmUgaXMgbm8gc3VjaCBmbG9vciAoc2hlIGF0dGVtcHRzIHRvIG1vdmUgaGlnaGVyIHRoYW4gdGhlIGgtdGggZmxvb3IpLCB0aGUgZWxldmF0b3IgZG9lc24mcnNxdW87dCBtb3ZlLjxcL3A+XHJcblxyXG48cD5UbyBwcm92ZSBoaXMgcGxhbiB3b3J0aHksIEVkd2FyZCB3YW50cyB0byBrbm93IGhvdyBtYW55IGZsb29ycyBhcmUgYWN0dWFsbHkgYWNjZXNzaWJsZSBmcm9tIHRoZSBmbHJzdCBmbG9vciB2aWEgaGlzIGVsZXZhdG9yLiBIZWxwIGhpbSBjYWxjdWxhdGUgdGhpcyBudW1iZXIuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgZmlsZSBjb250YWlucyBvbmUgaW50ZWdlciBoICZtZGFzaDsgdGhlIGhlaWdodCBvZiB0aGUgc2t5c2NyYXBlciAoMSAmbGU7IGggJmxlOyAxMDxzdXA+MTg8XC9zdXA+KTxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgYSwgYiBhbmQgYyAmbWRhc2g7IHRoZSBwYXJhbWV0ZXJzIG9mIHRoZSBidXR0b25zICgxICZsZTsgYSxiLGMgJmxlOyAxMDAsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBvbmUgaW50ZWdlciBudW1iZXIgJm1kYXNoOyB0aGUgbnVtYmVyIG9mIGZsb29ycyB0aGF0IGFyZSByZWFjaGFibGUgZnJvbSB0aGUgZmlyc3QgZmxvb3IuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d