캥거루 엄마

[!h]

캥거루 엄마가 새끼들을 자신의 주머니에 넣으려고 한다. 엄마에게는 새끼가 아주 많다. 가장 작은 두 마리는 각각 일 그램밖에 나가지 않지만, 그다음부터는 각 새끼의 무게가 바로 앞의 두 새끼의 무게를 합한 것과 같다. 따라서 가장 작은 새끼 여섯 마리의 무게는 1, 1, 2, 3, 5, 8그램이다.

엄마는 최대 $X$킬로그램까지 들 수 있다(단 일 그램도 더 들 수 없다). 엄마는 새끼를 몇 마리 데려갈 수 있는가?

입력은 정수 $X$이 주어지는 한 줄로 이루어져 있으며, $1\le X \le 1000$이고, 이 정수는 엄마가 들 수 있는 최대 킬로그램 수를 나타낸다.

프로그램은 무게의 합이 최대 $X$킬로그램인 새끼 수의 최댓값을 나타내는 정수 하나를 한 줄에 출력한다.