Sheep
TopCoder SRM 483
Time Limit: 0.7s, Memory Limit: 64MiB
След дълго въртене в леглото, Ели най-накрая заспа. За да постигне това, тя брои овце докато числото овърфлоуна и стана отрицателно. Сега момичето има странен сън. В него тя е на брега на река с нейното стадо от N овчици. От другата страна на реката се намират безкрайните поля от тучна трева, която нейните овчици бленуват толкова много. Тя иска да ги закара там, като за целта може да ползва лодка с неопределен капацитет. Ели се чуди колко най-малко трябва да е той, за да може тя да закара всички овчици от другата страна на реката с не повече от K пътувания (едно пътуване е отиване до другата страна и (евентуално) връщане обратно) – все пак нощта е кратка и тя не може да си позволи цяла нощ да вози овце.
Нейните овчици са с различни големини и тегло. Тя не знае как оптимално да ги взема в различните пътувания, затова решава да ползва следната стратегия. Всяко пътуване започва с празна лодка. В нея тя слага най-тежката овца, която се побира. След това тя взема следващата най-тежка овца, която се побира заедно с първата. Третата овца е следващата с най-голямо тегло, която не би претоварила лодката заедно с първите две. Тя продължава така да допълва лодката с овце, докато или е взела всички, или не може да натъпче никоя друга. След като лодката се напълни, тя закарва овцете от другата страна, разтоварва ги, и се връща с празна лодка за следващата партида. Ели е фино момиче, а и нейното тегло е константа, така че можем да не включваме в сметките.
Нека, например, овчиците имат тегла, съответно, 30, 15, 13, 8, 5, 3, 2, и 2. Ако капацитетът на лодката е 42, за да ги прекара, на нея ще са й нужни два курса, като на първия курс тя би взела овчиците с тегла 30, 8, и 3, а на втория – тези с тегла 15, 13, 5, 2, и 2. Ако капацитетът е 37, на нея ще са й нужни три курса: на първия ще са овцете с тегла 30, 5, и 2, на втория тези с 15, 13, и 8, и на последния – тези с 3 и 2.
Ако, ползвайки нейната стратегия, K курса не са достатъчни за превозването на всичките N овце, то значи избраният капацитет на лодката е неподходящ. По дадена информация за броя и теглото на овцете, а както и максималния брой курсове, които е склонна да направи Ели, изпечатайте най-малкия капацитет на лодката, с който момичето може да пренесе всички овце.
Нейните овчици са с различни големини и тегло. Тя не знае как оптимално да ги взема в различните пътувания, затова решава да ползва следната стратегия. Всяко пътуване започва с празна лодка. В нея тя слага най-тежката овца, която се побира. След това тя взема следващата най-тежка овца, която се побира заедно с първата. Третата овца е следващата с най-голямо тегло, която не би претоварила лодката заедно с първите две. Тя продължава така да допълва лодката с овце, докато или е взела всички, или не може да натъпче никоя друга. След като лодката се напълни, тя закарва овцете от другата страна, разтоварва ги, и се връща с празна лодка за следващата партида. Ели е фино момиче, а и нейното тегло е константа, така че можем да не включваме в сметките.
Нека, например, овчиците имат тегла, съответно, 30, 15, 13, 8, 5, 3, 2, и 2. Ако капацитетът на лодката е 42, за да ги прекара, на нея ще са й нужни два курса, като на първия курс тя би взела овчиците с тегла 30, 8, и 3, а на втория – тези с тегла 15, 13, 5, 2, и 2. Ако капацитетът е 37, на нея ще са й нужни три курса: на първия ще са овцете с тегла 30, 5, и 2, на втория тези с 15, 13, и 8, и на последния – тези с 3 и 2.
Ако, ползвайки нейната стратегия, K курса не са достатъчни за превозването на всичките N овце, то значи избраният капацитет на лодката е неподходящ. По дадена информация за броя и теглото на овцете, а както и максималния брой курсове, които е склонна да направи Ели, изпечатайте най-малкия капацитет на лодката, с който момичето може да пренесе всички овце.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N и K – съответно броят овце и максималният брой курсове. На втория ред ще бъдат зададени N цели числа W1, W2, ..., WN, задаващи теглата на овцете.
Изход
На единствен ред на стандартния изход изведете едно цяло число – минималния капацитет на лодката, който би позволил всички овце да бъдат закарани (ползвайки стратегията на Ели) с не повече от K курса.
Ограничения
- 1 ≤ N, K, Wi ≤ 2000
| Примерен Вход | Примерен Изход |
|---|---|
| 6 2 30 7 26 10 5 4 | 42 |
Капацитетът на лодката трябва да е поне 30, тъй като в противен случай най-тежката овца няма да може да бъде превозена. Все пак, 30 е недостатъчно за да могат да бъдат превозени всички овце в 2 курса – в първия тя ще вземе овцата с тегло 30, във втория, тези с тегло 26 и 4 и в третия – тези с тегла 10, 7 и 5. Най-малкият капацитет, който й позволява да ползва само 2 курса е 42. Първият курс ще вземе овцете с тегла 30 и 10, а вторият – тези с тегла 26, 7, 5 и 4.
Забележете, че съществува стратегия, с която капацитет 41 би бил достатъчен (да вземе първо тези с тегло 30, 7 и 4, а после тези с 26, 10 и 5), но Ели няма да използва нея.
| Примерен Вход | Примерен Изход |
|---|---|
| 200 20 42 468 335 501 1170 1725 1479 1359 963 465 1706 146 1282 828 1962 492 996 1943 828 1437 392 605 1903 154 293 383 1422 717 1719 1896 1448 1727 772 1539 1870 1913 1668 300 1036 1895 704 1812 1323 334 1674 665 1142 1712 254 869 1548 1645 663 758 38 860 724 1742 1530 779 317 1036 191 1843 289 107 1041 943 1265 649 1447 1806 1891 730 371 1351 1007 1102 394 1549 1630 624 85 1955 757 1841 967 1377 1932 309 945 440 627 1324 1538 1539 119 83 930 542 834 1116 640 1659 705 1931 1978 307 1674 387 1022 746 925 1073 271 1830 778 1574 1098 513 1987 1291 1162 637 356 768 1656 1575 32 53 1351 1151 942 1725 1967 1431 1108 192 8 1338 1458 288 1754 384 946 910 210 1759 222 589 423 947 1507 1031 414 1169 901 592 763 1656 1411 360 1625 538 1549 484 1596 42 1603 351 292 837 1375 1021 597 22 1349 1200 1669 485 282 735 54 2000 419 1939 901 1789 128 468 1729 894 649 484 1808 422 311 618 814 1515 | 9986 |
Във входните данни всички тегла на овцете ще са на един ред.