시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 1125 475 391 50.713%

문제

강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다. 참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다고 가정한다.

예를 들어, 다리의 길이 w는 2, 다리의 최대하중 L은 10, 다리를 건너려는 트럭이 트럭의 무게가 [7, 4, 5, 6]인 순서대로 다리를 오른쪽에서 왼쪽으로 건넌다고 하자. 이 경우 모든 트럭이 다리를 건너는 최단시간은 아래의 그림에서 보는 것과 같이 8 이다.

Figure 1. 본문의 예에 대해 트럭들이 다리를 건너는 과정.

다리의 길이와 다리의 최대하중, 그리고 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때, 모든 트럭이 다리를 건너는 최단시간을 구하는 프로그램을 작성하라.

입력

입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트럭의 수, w는 다리의 길이, 그리고 L은 다리의 최대하중을 나타낸다. 입력의 두 번째 줄에는 n개의 정수 a1, a2, ⋯ , an (1 ≤ ai ≤ 10)가 주어지는데, ai는 i번째 트럭의 무게를 나타낸다.

출력

출력은 표준출력을 사용한다. 모든 트럭들이 다리를 건너는 최단시간을 출력하라.

예제 입력 1

4 2 10
7 4 5 6

예제 출력 1

8

예제 입력 2

1 100 100
10

예제 출력 2

101

예제 입력 3

10 100 100
10 10 10 10 10 10 10 10 10 10

예제 출력 3

110
W3sicHJvYmxlbV9pZCI6IjEzMzM1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkMmI4XHViN2VkIiwiZGVzY3JpcHRpb24iOiI8cD5cdWFjMTVcdWM3NDQgXHVhYzAwXHViODVjXHVjOWMwXHViOTc0XHViMjk0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWNjMjhcdWMxMjBcdWM3M2NcdWI4NWMgXHViNDFjIFx1YjJlNFx1YjlhY1x1YWMwMCBcdWQ1NThcdWIwOTggXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViMmU0XHViOWFjXHViOTdjIG4gXHVhYzFjXHVjNzU4IFx1ZDJiOFx1YjdlZFx1Yzc3NCBcdWFjNzRcdWIxMDhcdWFjMDBcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWQyYjhcdWI3ZWRcdWM3NTggXHVjMjFjXHVjMTFjXHViMjk0IFx1YmMxNFx1YWZjMCBcdWMyMTggXHVjNWM2XHVjNzNjXHViYTcwLCBcdWQyYjhcdWI3ZWRcdWM3NTggXHViYjM0XHVhYzhjXHViMjk0IFx1YzExY1x1Yjg1YyBcdWFjMTlcdWM5YzAgXHVjNTRhXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjJlNFx1YjlhYyBcdWM3MDRcdWM1ZDBcdWIyOTQgXHViMmU4XHVjOWMwIHcgXHViMzAwXHVjNzU4IFx1ZDJiOFx1YjdlZFx1YjljYyBcdWIzZDlcdWMyZGNcdWM1ZDAgXHVjNjJjXHViNzdjXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjJlNFx1YjlhY1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgdyBcdWIyZThcdWM3MDRcdWFlMzhcdWM3NzQodW5pdCBkaXN0YW5jZSlcdWM3NzRcdWJhNzAsIFx1YWMwMSBcdWQyYjhcdWI3ZWRcdWI0ZTRcdWM3NDAgXHVkNTU4XHViMDk4XHVjNzU4IFx1YjJlOFx1YzcwNFx1YzJkY1x1YWMwNCh1bml0IHRpbWUpXHVjNWQwIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWIyZThcdWM3MDRcdWFlMzhcdWM3NzRcdWI5Y2NcdWQwN2NcdWI5Y2MgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTVjXHViMmU0LiBcdWIzZDlcdWMyZGNcdWM1ZDAgXHViMmU0XHViOWFjIFx1YzcwNFx1YzVkMCBcdWM2MmNcdWI3N2NcdWFjMDAgXHVjNzg4XHViMjk0IFx1ZDJiOFx1YjdlZFx1YjRlNFx1Yzc1OCBcdWJiMzRcdWFjOGNcdWM3NTggXHVkNTY5XHVjNzQwIFx1YjJlNFx1YjlhY1x1Yzc1OCBcdWNkNWNcdWIzMDBcdWQ1NThcdWM5MTFcdWM3NzggTFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjYzM4XHVhY2UwXHViODVjLCBcdWIyZTRcdWI5YWMgXHVjNzA0XHVjNWQwIFx1YzY0NFx1YzgwNFx1ZDc4OCBcdWM2MmNcdWI3N2NcdWFjMDBcdWM5YzAgXHViYWJiXHVkNTVjIFx1ZDJiOFx1YjdlZFx1Yzc1OCBcdWJiMzRcdWFjOGNcdWIyOTQgXHViMmU0XHViOWFjIFx1YzcwNFx1Yzc1OCBcdWQyYjhcdWI3ZWRcdWI0ZTRcdWM3NTggXHViYjM0XHVhYzhjXHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWFjYzRcdWMwYjBcdWQ1NjAgXHViNTRjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWIyZTRcdWI5YWNcdWM3NTggXHVhZTM4XHVjNzc0IHdcdWIyOTQgMiwgXHViMmU0XHViOWFjXHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1ZDU1OFx1YzkxMSBMXHVjNzQwIDEwLCBcdWIyZTRcdWI5YWNcdWI5N2MgXHVhYzc0XHViMTA4XHViODI0XHViMjk0IFx1ZDJiOFx1YjdlZFx1Yzc3NCBcdWQyYjhcdWI3ZWRcdWM3NTggXHViYjM0XHVhYzhjXHVhYzAwIFs3LCA0LCA1LCA2XVx1Yzc3OCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHViMmU0XHViOWFjXHViOTdjIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzVkMFx1YzExYyBcdWM2N2NcdWNhYmRcdWM3M2NcdWI4NWMgXHVhYzc0XHViMTBjXHViMmU0XHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjNzc0IFx1YWNiZFx1YzZiMCBcdWJhYThcdWI0ZTAgXHVkMmI4XHViN2VkXHVjNzc0IFx1YjJlNFx1YjlhY1x1Yjk3YyBcdWFjNzRcdWIxMDhcdWIyOTQgXHVjZDVjXHViMmU4XHVjMmRjXHVhYzA0XHVjNzQwIFx1YzU0NFx1Yjc5OFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWMgXHViY2Y0XHViMjk0IFx1YWM4M1x1YWNmYyBcdWFjMTlcdWM3NzQgOCBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3Byb2JsZW1cLzEzMzM1XC8xLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIxNHB4OyB3aWR0aDo2NjRweFwiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5GaWd1cmUgMS4gXHViY2Y4XHViYjM4XHVjNzU4IFx1YzYwOFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVkMmI4XHViN2VkXHViNGU0XHVjNzc0IFx1YjJlNFx1YjlhY1x1Yjk3YyBcdWFjNzRcdWIxMDhcdWIyOTQgXHVhY2ZjXHVjODE1LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWI5YWNcdWM3NTggXHVhZTM4XHVjNzc0XHVjNjQwIFx1YjJlNFx1YjlhY1x1Yzc1OCBcdWNkNWNcdWIzMDBcdWQ1NThcdWM5MTEsIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWIyZTRcdWI5YWNcdWI5N2MgXHVhYzc0XHViMTA4XHViODI0XHViMjk0IFx1ZDJiOFx1YjdlZFx1YjRlNFx1Yzc1OCBcdWJiMzRcdWFjOGNcdWFjMDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YmFhOFx1YjRlMCBcdWQyYjhcdWI3ZWRcdWM3NzQgXHViMmU0XHViOWFjXHViOTdjIFx1YWM3NFx1YjEwOFx1YjI5NCBcdWNkNWNcdWIyZThcdWMyZGNcdWFjMDRcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjUgXHViMzcwXHVjNzc0XHVkMTMwXHViMjk0IFx1ZDQ1Y1x1YzkwMFx1Yzc4NVx1YjgyNVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWI0NTAgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzEzOCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IG4gKDEgJmxlOyBuICZsZTsgMSwwMDApICwgdyAoMSAmbGU7IHcgJmxlOyAxMDApIGFuZCBMICgxMCAmbGU7IEwgJmxlOyAxLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwLCBuXHVjNzQwIFx1YjJlNFx1YjlhY1x1Yjk3YyBcdWFjNzRcdWIxMDhcdWIyOTQgXHVkMmI4XHViN2VkXHVjNzU4IFx1YzIxOCwgd1x1YjI5NCBcdWIyZTRcdWI5YWNcdWM3NTggXHVhZTM4XHVjNzc0LCBcdWFkZjhcdWI5YWNcdWFjZTAgTFx1Yzc0MCBcdWIyZTRcdWI5YWNcdWM3NTggXHVjZDVjXHViMzAwXHVkNTU4XHVjOTExXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzU4IFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IG5cdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IGE8c3ViPjE8XC9zdWI+LCBhPHN1Yj4yPFwvc3ViPiwgXHUyMmVmICwgYTxzdWI+bjxcL3N1Yj4gKDEgJmxlOyBhPHN1Yj5pPFwvc3ViPiAmbGU7IDEwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTRcdWIzNzAsIGE8c3ViPmk8XC9zdWI+XHViMjk0IGlcdWJjODhcdWM5ZjggXHVkMmI4XHViN2VkXHVjNzU4IFx1YmIzNFx1YWM4Y1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDljXHViODI1XHVjNzQwIFx1ZDQ1Y1x1YzkwMFx1Y2Q5Y1x1YjgyNVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWQyYjhcdWI3ZWRcdWI0ZTRcdWM3NzQgXHViMmU0XHViOWFjXHViOTdjIFx1YWM3NFx1YjEwOFx1YjI5NCBcdWNkNWNcdWIyZThcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEzMzM1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVHJ1Y2tzIiwiZGVzY3JpcHRpb24iOiI8cD5UaGVyZSBhcmUgbiBjYXJnbyB0cnVja3MgaW4gYSBsaW5lIHRvIGNyb3NzIGEgb25lIGxhbmUgd2lkZSBicmlkZ2Ugb3ZlciBhIHJpdmVyLiBUaGUgb3JkZXIgb2YgdHJ1Y2tzIGNhbm5vdCBiZSBjaGFuZ2VkIGFuZCB0aGUgd2VpZ2h0IG9mIGVhY2ggdHJ1Y2sgbWF5IG5vdCBiZSB0aGUgc2FtZS4gT25seSB3IHRydWNrcyBjYW4gYmUgb24gdGhlIGJyaWRnZSBhdCB0aGUgc2FtZSB0aW1lLiBXZSBhc3N1bWUgdGhhdCB0aGUgbGVuZ3RoIG9mIHRoZSBicmlkZ2UgaXMgdyB1bml0IGRpc3RhbmNlIGFuZCBlYWNoIHRydWNrIG1vdmVzIGEgdW5pdCBkaXN0YW5jZSBpbiBhIHVuaXQgdGltZS4gVGhlIHN1bSBvZiB0aGUgd2VpZ2h0cyBvZiB0aGUgdHJ1Y2tzIG9uIHRoZSBicmlkZ2Ugc2hvdWxkIGJlIGxlc3MgdGhhbiBvciBlcXVhbCB0byBMIGR1ZSB0byB0aGUgbWF4aW11bSBzYWZlIGxvYWQgb2YgdGhlIGJyaWRnZS4gTm90ZSB0aGF0IHRoZSB3ZWlnaHRzIG9mIHRydWNrcyB0aGF0IGFyZW4mcnNxdW87dCBmdWxseSBwcmVzZW50IG9uIHRoZSBicmlkZ2UgYXJlIG5vdCBjb25zaWRlcmVkIGluIHRoZSBsb2FkIGNhbGN1bGF0aW9uIG9mIHRoZSB0cnVja3Mgb24gdGhlIGJyaWRnZS48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGxldCB3IGJlIDIgYW5kIEwgYmUgMTAgYW5kIHRoZSBzZXF1ZW5jZSBvZiB0aGUgd2VpZ2h0cyBvZiB0aGUgdHJ1Y2tzIGJlIFs3LCA0LCA1LCA2XSBhbmQgdGhlIHRydWNrcyBhcmUgY3Jvc3NpbmcgZnJvbSByaWdodCB0byBsZWZ0LiBUaGVuLCB0aGUgZWFybGllc3QgdGltZSBmb3IgYWxsIHRoZSB0cnVja3MgdG8gY3Jvc3MgdGhlIGJyaWRnZSBpcyA4LCBhcyBpbGx1c3RyYXRlZCBpbiBGaWd1cmUgMS48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvMTMzMzVcLzEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjE0cHg7IHRleHQtYWxpZ246Y2VudGVyOyB3aWR0aDo2NjRweFwiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5GaWd1cmUgMS4gVHJ1Y2tzIGNyb3NzaW5nIHRoZSBicmlkZ2UuPFwvcD5cclxuXHJcbjxwPllvdSBhcmUgZ2l2ZW4gdGhlIG1heGltdW0gYWZmb3JkYWJsZSBudW1iZXIgb2YgdGhlIHRydWNrcyBvbiB0aGUgYnJpZGdlIGFuZCB0aGUgbWF4aW11bSBzYWZlIGxvYWQgb2YgdGhlIGJyaWRnZSBhbmQgdGhlIHNlcXVlbmNlIG9mIHRoZSB3ZWlnaHRzIG9mIHRoZSB0cnVja3MuIFdyaXRlIGEgcHJvZ3JhbSBmb3IgZmluZGluZyB0aGUgZWFybGllc3QgdGltZSBmb3IgdGhlIHRydWNrcyB0byBjcm9zcyB0aGUgYnJpZGdlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIHR3byBsaW5lcy4gVGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgbiAoMSAmbGU7IG4gJmxlOyAxLDAwMCksIHcgKDEgJmxlOyB3ICZsZTsgMTAwKSBhbmQgTCAoMTAgJmxlOyBMICZsZTsgMSwwMDApIHdoZXJlIG4gaXMgdGhlIG51bWJlciBvZiB0cnVja3MgdG8gY3Jvc3MgdGhlIGJyaWRnZSwgdyBpcyB0aGUgbWF4aW11bSBhZmZvcmRhYmxlIG51bWJlciBvZiB0cnVja3Mgb24gdGhlIGJyaWRnZSBhbmQgTCBpcyB0aGUgbWF4aW11bSBzYWZlIGxvYWQgb2YgdGhlIGJyaWRnZS4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIG4gaW50ZWdlcnMgYTxzdWI+MTxcL3N1Yj4sIGE8c3ViPjI8XC9zdWI+LCBcdTIyZWYgLCBhPHN1Yj5uPFwvc3ViPiAoMSAmbGU7IGE8c3ViPmk8XC9zdWI+ICZsZTsgMTApLCB3aGVyZSBhPHN1Yj5pPFwvc3ViPiByZXByZXNlbnRzIHRoZSB3ZWlnaHQgb2YgaS10aCB0cnVjay48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCB0aGUgZWFybGllc3QgdGltZSB0byBjcm9zcyB0aGUgYnJpZGdlLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==