#include<algorithm>
#include<iostream>
int GetScalingFactor(int input)
{
const unsigned int inputs[] = {13107, 19660, 26214, 32767, 39321, 45874, 52428, 58981};
const int factors[] = {72816, 81918, 93621, 109225, 131070, 163837, 218450, 327675, 0};
auto it = std::lower_bound(std::begin(inputs), std::end(inputs), input + 1);
return factors[std::distance(std::begin(inputs), it)];
}
int main()
{
std::cout << GetScalingFactor(100) << std::endl;
std::cout << GetScalingFactor(13107) << std::endl;
std::cout << GetScalingFactor(15000) << std::endl;
std::cout << GetScalingFactor(20000) << std::endl;
std::cout << GetScalingFactor(30000) << std::endl;
std::cout << GetScalingFactor(35000) << std::endl;
std::cout << GetScalingFactor(40000) << std::endl;
std::cout << GetScalingFactor(45875) << std::endl;
std::cout << GetScalingFactor(55000) << std::endl;
std::cout << GetScalingFactor(60000) << std::endl;
}
CiNpbmNsdWRlPGFsZ29yaXRobT4KI2luY2x1ZGU8aW9zdHJlYW0+CgppbnQgR2V0U2NhbGluZ0ZhY3RvcihpbnQgaW5wdXQpCnsKICAgIGNvbnN0IHVuc2lnbmVkIGludCBpbnB1dHNbXSA9ICB7MTMxMDcsIDE5NjYwLCAyNjIxNCwgMzI3NjcsIDM5MzIxLCA0NTg3NCwgNTI0MjgsIDU4OTgxfTsKICAgIGNvbnN0IGludCBmYWN0b3JzW10gPSB7NzI4MTYsIDgxOTE4LCA5MzYyMSwgMTA5MjI1LCAxMzEwNzAsIDE2MzgzNywgMjE4NDUwLCAzMjc2NzUsIDB9OwoKICAgIGF1dG8gaXQgPSBzdGQ6Omxvd2VyX2JvdW5kKHN0ZDo6YmVnaW4oaW5wdXRzKSwgc3RkOjplbmQoaW5wdXRzKSwgaW5wdXQgKyAxKTsKICAgIHJldHVybiBmYWN0b3JzW3N0ZDo6ZGlzdGFuY2Uoc3RkOjpiZWdpbihpbnB1dHMpLCBpdCldOwp9CgppbnQgbWFpbigpCnsKICAgIHN0ZDo6Y291dCA8PCBHZXRTY2FsaW5nRmFjdG9yKDEwMCkgPDwgc3RkOjplbmRsOwogICAgc3RkOjpjb3V0IDw8IEdldFNjYWxpbmdGYWN0b3IoMTMxMDcpIDw8IHN0ZDo6ZW5kbDsKICAgIHN0ZDo6Y291dCA8PCBHZXRTY2FsaW5nRmFjdG9yKDE1MDAwKSA8PCBzdGQ6OmVuZGw7CiAgICBzdGQ6OmNvdXQgPDwgR2V0U2NhbGluZ0ZhY3RvcigyMDAwMCkgPDwgc3RkOjplbmRsOwogICAgc3RkOjpjb3V0IDw8IEdldFNjYWxpbmdGYWN0b3IoMzAwMDApIDw8IHN0ZDo6ZW5kbDsKICAgIHN0ZDo6Y291dCA8PCBHZXRTY2FsaW5nRmFjdG9yKDM1MDAwKSA8PCBzdGQ6OmVuZGw7CiAgICBzdGQ6OmNvdXQgPDwgR2V0U2NhbGluZ0ZhY3Rvcig0MDAwMCkgPDwgc3RkOjplbmRsOwogICAgc3RkOjpjb3V0IDw8IEdldFNjYWxpbmdGYWN0b3IoNDU4NzUpIDw8IHN0ZDo6ZW5kbDsKICAgIHN0ZDo6Y291dCA8PCBHZXRTY2FsaW5nRmFjdG9yKDU1MDAwKSA8PCBzdGQ6OmVuZGw7CiAgICBzdGQ6OmNvdXQgPDwgR2V0U2NhbGluZ0ZhY3Rvcig2MDAwMCkgPDwgc3RkOjplbmRsOwp9