문제
이사를 온 은하는 마침내 $M$대의 전자기기와 $N$대의 멀티탭을 모두 새 집에 옮겼습니다. 멀티탭의 길이는 무한합니다.
새 집에는 $K$개의 벽면 콘센트가 있습니다. $(K \le M)$ 은하는 가져온 멀티탭을 활용해 전자기기들에 전기를 연결하려고 합니다. 어떤 멀티탭을 다른 멀티탭 소켓에 꽂아도 됩니다. 다만 일부 기기는 전력 사용량이 많아서, 전기가 콘센트로부터 기기까지 일정 수 초과의 멀티탭을 거치는 경우 전자기기에 과부하가 걸려 불이 나게 될 수도 있습니다.
이런 상황에서 최대한 많은 대수의 전자기기에 전기를 공급받을 수 있게 할 수 있나요?
출력
주어진 상황에서 가능한 한 많은 장치들이 전기를 공급받을 수 있게 할 때, 전기를 공급받게 되는 장치의 수를 출력하세요.
W3sicHJvYmxlbV9pZCI6IjMxMzk2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhY2ZjXHViZDgwXHVkNTU4IFx1YmMyOVx1YzljMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNzc0XHVjMGFjXHViOTdjIFx1YzYyOCBcdWM3NDBcdWQ1NThcdWIyOTQgXHViOWM4XHVjZTY4XHViMGI0ICRNJFx1YjMwMFx1Yzc1OCBcdWM4MDRcdWM3OTBcdWFlMzBcdWFlMzBcdWM2NDAgJE4kXHViMzAwXHVjNzU4IFx1YmE0MFx1ZDJmMFx1ZDBlZFx1Yzc0NCBcdWJhYThcdWI0NTAgXHVjMGM4IFx1YzlkMVx1YzVkMCBcdWM2MmVcdWFjYmNcdWMyYjVcdWIyYzhcdWIyZTQuIFx1YmE0MFx1ZDJmMFx1ZDBlZFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHViYjM0XHVkNTVjXHVkNTY5XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzggXHVjOWQxXHVjNWQwXHViMjk0ICRLJFx1YWMxY1x1Yzc1OCBcdWJjYmRcdWJhNzQgXHVjZjU4XHVjMTNjXHVkMmI4XHVhYzAwIFx1Yzc4OFx1YzJiNVx1YjJjOFx1YjJlNC4gJChLIFxcbGUgTSkkIFx1Yzc0MFx1ZDU1OFx1YjI5NCBcdWFjMDBcdWM4MzhcdWM2MjggXHViYTQwXHVkMmYwXHVkMGVkXHVjNzQ0IFx1ZDY1Y1x1YzZhOVx1ZDU3NCBcdWM4MDRcdWM3OTBcdWFlMzBcdWFlMzBcdWI0ZTRcdWM1ZDAgXHVjODA0XHVhZTMwXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NjlcdWIyYzhcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWJhNDBcdWQyZjBcdWQwZWRcdWM3NDQgXHViMmU0XHViOTc4IFx1YmE0MFx1ZDJmMFx1ZDBlZCBcdWMxOGNcdWNmMTNcdWM1ZDAgXHVhZjQyXHVjNTQ0XHViM2M0IFx1YjQyOVx1YjJjOFx1YjJlNC4gXHViMmU0XHViOWNjIFx1Yzc3Y1x1YmQ4MCBcdWFlMzBcdWFlMzBcdWIyOTQgXHVjODA0XHViODI1IFx1YzBhY1x1YzZhOVx1YjdjOVx1Yzc3NCBcdWI5Y2VcdWM1NDRcdWMxMWMsIFx1YzgwNFx1YWUzMFx1YWMwMCBcdWNmNThcdWMxM2NcdWQyYjhcdWI4NWNcdWJkODBcdWQxMzAgXHVhZTMwXHVhZTMwXHVhZTRjXHVjOWMwIFx1Yzc3Y1x1YzgxNSBcdWMyMTggXHVjZDA4XHVhY2ZjXHVjNzU4IFx1YmE0MFx1ZDJmMFx1ZDBlZFx1Yzc0NCBcdWFjNzBcdWNlNThcdWIyOTQgXHVhY2JkXHVjNmIwIFx1YzgwNFx1Yzc5MFx1YWUzMFx1YWUzMFx1YzVkMCBcdWFjZmNcdWJkODBcdWQ1NThcdWFjMDAgXHVhYzc4XHViODI0IFx1YmQ4OFx1Yzc3NCBcdWIwOThcdWFjOGMgXHViNDIwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWMyYjVcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YjdmMCBcdWMwYzFcdWQ2NjlcdWM1ZDBcdWMxMWMgXHVjZDVjXHViMzAwXHVkNTVjIFx1YjljZVx1Yzc0MCBcdWIzMDBcdWMyMThcdWM3NTggXHVjODA0XHVjNzkwXHVhZTMwXHVhZTMwXHVjNWQwIFx1YzgwNFx1YWUzMFx1Yjk3YyBcdWFjZjVcdWFlMDlcdWJjMWJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YWM4YyBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjA5OFx1YzY5ND88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHViYTQwXHVkMmYwXHVkMGVkXHVjNzU4IFx1YzIxOCAkTiQsIFx1YmNiZCBcdWNmNThcdWMxM2NcdWQyYjhcdWM3NTggXHVjMjE4ICRLJCwgXHVjODA0XHVhZTMwXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YWNlMFx1Yzc5MCBcdWQ1NThcdWIyOTQgXHVjODA0XHVjNzkwXHVhZTMwXHVhZTMwXHVjNzU4IFx1YzIxOCAkTSRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuICQoMSBcXGxlIE4gXFxsZSAyMDBcXCwwMDA7JCAkMSBcXGxlIEsgXFxsZSBNIFxcbGUgMjAwXFwsMDAwKSQ8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjMDEgXHViYTQwXHVkMmYwXHVkMGVkXHVjNzU4IFx1YzE4Y1x1Y2YxMyBcdWMyMThcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTU4XHViMjk0ICROJFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggJEFfMSxcXGNkb3RzLEFfTiRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuICQoMSBcXGxlIEFfaSBcXGxlIDIwMFxcLDAwMCkkPFwvcD5cclxuXHJcbjxwPlx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViY2JkIFx1Y2Y1OFx1YzEzY1x1ZDJiOFx1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWFjMDEgXHVjODA0XHVjNzkwXHVhZTMwXHVhZTMwXHVhZTRjXHVjOWMwIFx1YmE4NyBcdWFjMWNcdWFlNGNcdWM5YzBcdWM3NTggXHViYTQwXHVkMmYwXHVkMGVkXHVjNzQ0IFx1YWM3MFx1Y2U2MCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwXHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YjI5NCAkTSRcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4ICREXzEsXFxjZG90cyxEX00kXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LiBcdWM4MDRcdWM3OTBcdWFlMzBcdWFlMzBcdWI4NWMgXHVhYzAwXHViMjk0XHViMzcwIFx1YWM3OFx1Y2U1YyBcdWJhNDBcdWQyZjBcdWQwZWRcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0LCBcdWM4MDRcdWM3OTBcdWFlMzBcdWFlMzBcdWFlNGNcdWM5YzAgXHVjODA0XHViOTU4XHVhYzAwIFx1ZDc1MFx1Yjk3NFx1YjI5NCBcdWIzZDlcdWM1NDggXHViOWNjXHViMDk4XHViMjk0IFx1YmE0MFx1ZDJmMFx1ZDBlZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3ODVcdWIyYzhcdWIyZTQuICQoMCBcXGxlIERfaSBcXGxlIDIwMFxcLDAwMCkkPFwvcD5cclxuXHJcbjxwPiREX2k9MCRcdWM3NzggXHVjODA0XHVjNzkwXHVhZTMwXHVhZTMwXHViMjk0IFx1YmNiZCBcdWNmNThcdWMxM2NcdWQyYjhcdWM1ZDBcdWI5Y2MgXHVjNWYwXHVhY2IwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWMyYjVcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjOGZjXHVjNWI0XHVjOWM0IFx1YzBjMVx1ZDY2OVx1YzVkMFx1YzExYyBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVkNTVjIFx1YjljZVx1Yzc0MCBcdWM3YTVcdWNlNThcdWI0ZTRcdWM3NzQgXHVjODA0XHVhZTMwXHViOTdjIFx1YWNmNVx1YWUwOVx1YmMxYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHVhYzhjIFx1ZDU2MCBcdWI1NGMsIFx1YzgwNFx1YWUzMFx1Yjk3YyBcdWFjZjVcdWFlMDlcdWJjMWJcdWFjOGMgXHViNDE4XHViMjk0IFx1YzdhNVx1Y2U1OFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjMTM4XHVjNjk0LjxcL3A+IiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzEzOTYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJPdmVybG9hZCBQcmV2ZW50aW9uIiwiZGVzY3JpcHRpb24iOiI8cD5FdW5oYSByZWNlbnRseSBtb3ZlZCB0byBhIG5ldyBob3VzZSBhbmQgYnJvdWdodCBhbGwgaGVyICRNJCBlbGVjdHJvbmljIGRldmljZXMgYW5kICROJCBwb3dlciBzdHJpcHMuIFRoZSBjb3JkIGZvciBlYWNoIHBvd2VyIHN0cmlwIGlzIGluZmluaXRlLjxcL3A+XHJcblxyXG48cD5UaGUgbmV3IGhvdXNlIGhhcyAkSyQgcG93ZXIgc29ja2V0cyBvbiB0aGUgd2FsbC4gJChLIFxcbGUgTSkkIEV1bmhhIHBsYW5zIHRvIHVzZSB0aGUgcG93ZXIgc3RyaXBzIHRvIHN1cHBseSBwb3dlciB0byB0aGUgZWxlY3Ryb25pYyBkZXZpY2VzLiZuYnNwO1lvdSBtYXkgcGx1ZyBhIHBvd2VyIHN0cmlwIGludG8gYSBzb2NrZXQgb2Ygb3RoZXIgcG93ZXIgc3RyaXBzLiZuYnNwO0hvd2V2ZXIsIHRoZSBwb3dlciBjb25zdW1wdGlvbiBmb3Igc29tZSBkZXZpY2VzIGlzIHZlcnkgbGFyZ2UgYW5kIG1heSBjYXVzZSBhbiBvdmVybG9hZCBpZiB0aGUgY29ubmVjdGlvbiZuYnNwO2Nyb3NzZXMgdG9vIG1hbnkgcG93ZXIgc3RyaXBzLjxcL3A+XHJcblxyXG48cD5XaGF0IGlzIHRoZSBsYXJnZXN0IHBvc3NpYmxlJm5ic3A7bnVtYmVyIG9mIGRldmljZXMgRXVuaGEgY2FuIHN1cHBseSBwb3dlciB0bz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyAkTiQsIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgcG93ZXIgc3RyaXBzLCAkSyQsIGRlbm90aW5nJm5ic3A7dGhlIG51bWJlciBvZiBwb3dlciBzb2NrZXRzIG9uIHRoZSB3YWxsLCBhbmQgJE0kLCBkZW5vdGluZyB0aGUgbnVtYmVyIG9mIGVsZWN0cm9uaWMgZGV2aWNlcy4mbmJzcDskKDEgXFxsZSBOIFxcbGUgMjAwXFwsMDAwOyQgJDEgXFxsZSBLIFxcbGUgTSBcXGxlIDIwMFxcLDAwMCkkPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyAkTiQgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzJm5ic3A7JEFfMSxcXGNkb3RzLEFfTiQsIGRlbm90aW5nIHRoZSBudW1iZXIgb2Ygc29ja2V0cyBvbiZuYnNwO2VhY2ggcG93ZXIgc3RyaXAuJm5ic3A7JCgxIFxcbGUgQV9pIFxcbGUgMjAwXFwsMDAwKSQ8XC9wPlxyXG5cclxuPHA+VGhlIHRoaXJkIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgJE0kIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyAkRF8xLFxcY2RvdHMsRF9NJCwgZGVub3RpbmcgdGhlIG1heGltdW0gbnVtYmVyIG9mIHBvd2VyIHN0cmlwcyZuYnNwO2VhY2ggZGV2aWNlIGNhbiBjcm9zcyBpbiBpdHMgY29ubmVjdGlvbiB0byZuYnNwO2EmbmJzcDt3YWxsIHNvY2tldC4mbmJzcDtUaGUgbnVtYmVyIG9mIGNyb3NzaW5nIHBvd2VyIHN0cmlwcyBvZiB0aGUgZGV2aWNlIGlzIHRoZSBudW1iZXIgb2YgcG93ZXIgc3RyaXBzIHRocm91Z2ggd2hpY2ggY3VycmVudCBmbG93cyB0byByZWFjaCB0aGUgZGV2aWNlLjxcL3A+XHJcblxyXG48cD4kKDAgXFxsZSBEX2kgXFxsZSAyMDBcXCwwMDApJDxcL3A+XHJcblxyXG48cD5JZiAkRF9pPTAkLCB0aGF0IGRldmljZSZuYnNwO2NhbiBvbmx5IGJlIGNvbm5lY3RlZCB0byBhIHdhbGwgc29ja2V0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkluIHRoZSBnaXZlbiBjb25kaXRpb25zLCBmaW5kIHRoZSBsYXJnZXN0IG51bWJlciBvZiBkZXZpY2VzIEV1bmhhIGNhbiBzdXBwbHkgcG93ZXIgdG8uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==