A. Нууцууд

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Жералд чөлөөт цагаараа улсын нууц зардаг. Бүх нууцууд адил $n$ маркын үнэтэй байдаг. Жералдын нууц борлуулж байгаа хотод цаасан мөнгө байдаггүй зөвхөн зооснууд байдаг. Зооснуудийн төрөл нь зөвхөн гуравтын зэргүүд байдаг: 1 марк, 3 марк, 9 марк, 27 марк г.м. Өөр төрлийн зоос байдаггүй. Жералд мөнгө хариулж өгөх дургүй учир бух худалдан авагч нар нь түүнийг хүндэтгээд боломжтой бол мөнгөө яг тааруулж өгдөг. Гэхдээ ийм явдал түүнд үргэлж тохиолдохгүй.

Нэгэн өдөр түүн дээр азгүй худалдан авагч ирж гэнэ. Түүнд яг таарсан мөнгө байсангүй. Тиймээс тэр бүх зоосоо гаргаж ирээд Жералдад хэрэгтэй мөнгнөөс нь бага зэрэг илүүг өгөхийг оролдов. Түүний авч чадах хамгийн их зоос хэд вэ?

Илүү тодорхой хэлье: бид худалдан авагчийн болгож чадахгүй $n$ маркаас их бүх үүсгэх боломжтой тоог авч үзнэ. Тэр бүрдээ тэр маркийг бүтээх хамгийн бага тооны зоосыг олно. Тэр дундаас хамгийн баша зоосоор бүтэх хамгийн их маркыг гаргана. Энэ тоо нь бидний хариу болох юм.

Оролт

Эхний мөрөнд $n$ ($1 ≤ n ≤ 10^{17}$) тоо өгөгдөнө.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.

Гаралт

Ганц мөрөнд азгүй худалдан авагчийн төлсөн байж болох хамгийн их маркыг хэвлэнэ.

Орчуулсан: Энхсанаа

Жишээ тэстүүд

Оролт
1
Гаралт
1
Оролт
4
Гаралт
2

Тэмдэглэл

In the first test case, if a buyer has exactly one coin of at least 3 marks, then, to give Gerald one mark, he will have to give this coin. In this sample, the customer can not have a coin of one mark, as in this case, he will be able to give the money to Gerald without any change.

In the second test case, if the buyer had exactly three coins of 3 marks, then, to give Gerald 4 marks, he will have to give two of these coins. The buyer cannot give three coins as he wants to minimize the number of coins that he gives.

Сэтгэгдлүүдийг ачааллаж байна...