시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 207 55 30 30.928%

문제

동호는 주식으로 떼돈을 벌려고 한다.  동호가 주식왕이라 불리는 이유는 미래의 주식 값의 변화까지도 정확히 예측하기 때문이다. 현재 동호는 C개의 주식을 눈여겨보고 있고 이 주식들을 일정한 기간동안 적당히 사고팔면서 돈을 부풀릴 계획이다.

  Day 1 Day 2 Day 3
주식 1 10 15 15
주식 2 13 11 20

위와 같이 각 주식에 대해 날짜에 따른 주식 비용이다. 처음 동호가 가지고 있는 자본이 10이라 할 때 3일동안 동호가 최대로 돈을 벌 수 있는 방법은 첫째 날 주식 1을 매입한다. 둘째 날 주식 1을 매각하고 주식 2를 매입한다. 셋째 날 주식 2를 매각하면 초기 자본을 포함하여 총 24의 돈을 갖게 된다.

문제는 주식 종류와 기간, 초기 자금 등이 주어졌을 때 동호가 최종적으로 가질 수 있는 돈의 최대값을 구하는 것이다.

입력

첫 줄에는 주식의 개수 C(1 ≤ N ≤ 50)과 주식 매입 및 매각을 할 기간 D(2 ≤ D ≤ 10), 초기 자금 M(1 ≤ M ≤ 200,000)이 공백으로 구분되어 주어진다. 두 번째 줄부터 C+1번째 줄까지 각 줄에는 각각 주식이 날짜에 따라 변하는 값이 입력된다.

출력

첫 줄에 동호가 최종적으로 가질 수 있는 돈의 최댓값을 출력한다. 출력값이 500,000을 넘지 않는 데이터만 주어진다.

예제 입력 1

2 3 10
10 15 15
13 11 20

예제 출력 1

24
W3sicHJvYmxlbV9pZCI6IjEyMzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4ZmNcdWMyZGRcdWM2NTUgXHViM2Q5XHVkNjM4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIzZDlcdWQ2MzhcdWIyOTQgXHVjOGZjXHVjMmRkXHVjNzNjXHViODVjIFx1YjViY1x1YjNjOFx1Yzc0NCBcdWJjOGNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiZuYnNwOyBcdWIzZDlcdWQ2MzhcdWFjMDAgXHVjOGZjXHVjMmRkXHVjNjU1XHVjNzc0XHViNzdjIFx1YmQ4OFx1YjlhY1x1YjI5NCBcdWM3NzRcdWM3MjBcdWIyOTQgXHViYmY4XHViNzk4XHVjNzU4IFx1YzhmY1x1YzJkZCBcdWFjMTJcdWM3NTggXHViY2MwXHVkNjU0XHVhZTRjXHVjOWMwXHViM2M0IFx1YzgxNVx1ZDY1NVx1ZDc4OCBcdWM2MDhcdWNlMjFcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LiBcdWQ2MDRcdWM3YWMgXHViM2Q5XHVkNjM4XHViMjk0IENcdWFjMWNcdWM3NTggXHVjOGZjXHVjMmRkXHVjNzQ0IFx1YjIwOFx1YzVlY1x1YWNhOFx1YmNmNFx1YWNlMCBcdWM3ODhcdWFjZTAgXHVjNzc0IFx1YzhmY1x1YzJkZFx1YjRlNFx1Yzc0NCBcdWM3N2NcdWM4MTVcdWQ1NWMgXHVhZTMwXHVhYzA0XHViM2Q5XHVjNTQ4IFx1YzgwMVx1YjJmOVx1ZDc4OCBcdWMwYWNcdWFjZTBcdWQzMTRcdWJhNzRcdWMxMWMgXHViM2M4XHVjNzQ0IFx1YmQ4MFx1ZDQ4MFx1YjliNCBcdWFjYzRcdWQ2OGRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDozMCVcIj5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4mbmJzcDs8XC90ZD5cclxuXHRcdFx0PHRkPkRheSAxPFwvdGQ+XHJcblx0XHRcdDx0ZD5EYXkgMjxcL3RkPlxyXG5cdFx0XHQ8dGQ+RGF5IDM8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+XHVjOGZjXHVjMmRkIDE8XC90ZD5cclxuXHRcdFx0PHRkPjEwPFwvdGQ+XHJcblx0XHRcdDx0ZD4xNTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTU8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+XHVjOGZjXHVjMmRkIDI8XC90ZD5cclxuXHRcdFx0PHRkPjEzPFwvdGQ+XHJcblx0XHRcdDx0ZD4xMTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MjA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwPlx1YzcwNFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVhYzAxIFx1YzhmY1x1YzJkZFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHViMGEwXHVjOWRjXHVjNWQwIFx1YjUzMFx1Yjk3OCBcdWM4ZmNcdWMyZGQgXHViZTQ0XHVjNmE5XHVjNzc0XHViMmU0LiBcdWNjOThcdWM3NGMgXHViM2Q5XHVkNjM4XHVhYzAwIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjNzkwXHViY2Y4XHVjNzc0IDEwXHVjNzc0XHViNzdjIFx1ZDU2MCBcdWI1NGMgM1x1Yzc3Y1x1YjNkOVx1YzU0OCBcdWIzZDlcdWQ2MzhcdWFjMDAgXHVjZDVjXHViMzAwXHViODVjIFx1YjNjOFx1Yzc0NCBcdWJjOGMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDAgXHVjY2FiXHVjOWY4IFx1YjBhMCBcdWM4ZmNcdWMyZGQgMVx1Yzc0NCBcdWI5ZTRcdWM3ODVcdWQ1NWNcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWIwYTAgXHVjOGZjXHVjMmRkIDFcdWM3NDQgXHViOWU0XHVhYzAxXHVkNTU4XHVhY2UwIFx1YzhmY1x1YzJkZCAyXHViOTdjIFx1YjllNFx1Yzc4NVx1ZDU1Y1x1YjJlNC4gXHVjMTRiXHVjOWY4IFx1YjBhMCBcdWM4ZmNcdWMyZGQgMlx1Yjk3YyBcdWI5ZTRcdWFjMDFcdWQ1NThcdWJhNzQgXHVjZDA4XHVhZTMwIFx1Yzc5MFx1YmNmOFx1Yzc0NCBcdWQzZWNcdWQ1NjhcdWQ1NThcdWM1ZWMgXHVjZDFkIDI0XHVjNzU4IFx1YjNjOFx1Yzc0NCBcdWFjMTZcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM4MWNcdWIyOTQgXHVjOGZjXHVjMmRkIFx1Yzg4NVx1Yjk1OFx1YzY0MCBcdWFlMzBcdWFjMDQsIFx1Y2QwOFx1YWUzMCBcdWM3OTBcdWFlMDggXHViNGYxXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMgXHViM2Q5XHVkNjM4XHVhYzAwIFx1Y2Q1Y1x1Yzg4NVx1YzgwMVx1YzczY1x1Yjg1YyBcdWFjMDBcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWIzYzhcdWM3NTggXHVjZDVjXHViMzAwXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzhmY1x1YzJkZFx1Yzc1OCBcdWFjMWNcdWMyMTggQygxICZsZTsgTiAmbGU7IDUwKVx1YWNmYyBcdWM4ZmNcdWMyZGQgXHViOWU0XHVjNzg1IFx1YmMwZiBcdWI5ZTRcdWFjMDFcdWM3NDQgXHVkNTYwIFx1YWUzMFx1YWMwNCBEKDIgJmxlOyBEICZsZTsgMTApLCBcdWNkMDhcdWFlMzAgXHVjNzkwXHVhZTA4IE0oMSAmbGU7IE0gJmxlOyAyMDAsMDAwKVx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgQysxXHViYzg4XHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMCBcdWFjMDEgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMVx1YWMwMSBcdWM4ZmNcdWMyZGRcdWM3NzQgXHViMGEwXHVjOWRjXHVjNWQwIFx1YjUzMFx1Yjc3YyBcdWJjYzBcdWQ1NThcdWIyOTQgXHVhYzEyXHVjNzc0IFx1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1YjNkOVx1ZDYzOFx1YWMwMCBcdWNkNWNcdWM4ODVcdWM4MDFcdWM3M2NcdWI4NWMgXHVhYzAwXHVjOWM4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViM2M4XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Y2Q5Y1x1YjgyNVx1YWMxMlx1Yzc3NCA1MDAsMDAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTQgXHViMzcwXHVjNzc0XHVkMTMwXHViOWNjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMjMxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3RvY2sgTWFya2V0IiwiZGVzY3JpcHRpb24iOiI8cD5EZXNwaXRlIHRoZWlyIGlubmF0ZSBwcnVkZW5jZSwgdGhlIGNvd3MgdG9vayBhIGJlYXRpbmcgaW4gdGhlIGhvbWUgbW9ydGdhZ2UgbWFya2V0IGFuZCBub3cgYXJlIHRyeWluZyB0aGVpciBoYW5kIGF0IHN0b2Nrcy4gSGFwcGlseSwgQmVzc2llIGlzIHByZXNjaWVudCBhbmQga25vd3Mgbm90IG9ubHkgdG9kYXkmIzM5O3MgUyAoMiAmbHQ7PSBTICZsdDs9IDUwKSBzdG9jayBwcmljZXMgYnV0IGFsc28gdGhlIGZ1dHVyZSBzdG9jayBwcmljZXMgZm9yIGEgdG90YWwgb2YgRCBkYXlzICgyICZsdDs9IEQgJmx0Oz0gMTApLjxcL3A+XHJcblxyXG48cD5HaXZlbiB0aGUgbWF0cml4IG9mIGN1cnJlbnQgYW5kIGZ1dHVyZSBzdG9jayBwcmljZXMgb24gdmFyaW91cyBkYXlzICgxICZsdDs9IFBSX3NkICZsdDs9IDEsMDAwKSBhbmQgYW4gaW5pdGlhbCBNICgxICZsdDs9IE0gJmx0Oz0gMjAwLDAwMCkgdW5pdHMgb2YgbW9uZXksIGRldGVybWluZSBhbiBvcHRpbWFsIGJ1eWluZyBhbmQgc2VsbGluZyBzdHJhdGVneSBpbiBvcmRlciB0byBtYXhpbWl6ZSB0aGUgZ2FpbiByZWFsaXplZCBieSBzZWxsaW5nIHN0b2NrIG9uIHRoZSBmaW5hbCBkYXkuIFNoYXJlcyBtdXN0IGJlIHB1cmNoYXNlZCBpbiBpbnRlZ2VyIG11bHRpcGxlcywgYW5kIHlvdSBuZWVkIG5vdCBzcGVuZCBhbGwgdGhlIG1vbmV5IChvciBhbnkgbW9uZXkpLiBJdCBpcyBndWFyYW50ZWVkIHRoYXQgeW91IHdpbGwgbm90IGJlIGFibGUgdG8gZWFybiBhIHByb2ZpdCBvZiBtb3JlIHRoYW4gNTAwLDAwMCB1bml0cyBvZiBtb25leS48XC9wPlxyXG5cclxuPHA+Q29uc2lkZXIgdGhlIGV4YW1wbGUgYmVsb3cgb2YgYSBidWxsIChpLmUuLCBpbXByb3ZpbmcpIG1hcmtldCwgdGhlIGtpbmQgQmVzc2llIGxpa2VzIG1vc3QuIEluIHRoaXMgY2FzZSwgUz0yIHN0b2NrcyBhbmQgRD0zIGRheXMuIFRoZSBjb3dzIGhhdmUgMTAgdW5pdHMgb2YgbW9uZXkgdG8gaW52ZXN0LjxcL3A+XHJcblxyXG48cHJlPlxyXG4gICAgICAgICAgICAgICAgICAgVG9kYXkmIzM5O3MgcHJpY2VcclxuICAgICAgICAgICAgICAgICAgIHwgICBUb21vcnJvdyYjMzk7cyBwcmljZVxyXG4gICAgICAgICAgICAgICAgICAgfCAgIHwgIFR3byBkYXlzIGhlbmNlXHJcbiAgICAgICAgICAgICBTdG9jayB8ICAgfCAgfCBcclxuICAgICAgICAgICAgICAxICAgIDEwIDE1IDE1XHJcbiAgICAgICAgICAgICAgMiAgICAxMyAxMSAyMFxyXG48XC9wcmU+XHJcblxyXG48cD5JZiBtb25leSBpcyB0byBiZSBtYWRlLCB0aGUgY293cyBtdXN0IHB1cmNoYXNlIHN0b2NrIDEgb24gZGF5IDEuIFNlbGxpbmcgc3RvY2sgMSBvbiBkYXkgMiBhbmQgcXVpY2tseSBidXlpbmcgc3RvY2sgMiB5aWVsZHMgNCBtb25leSBpbiB0aGUgYmFuayBhbmQgb25lIHNoYXJlIG9mIDIuIFNlbGxpbmcgc3RvY2sgMiBvbiB0aGUgZmluYWwgZGF5IGJyaW5ncyBpbiAyMCBtb25leSBmb3IgYSB0b3RhbCBvZiAyNCBtb25leSB3aGVuIHRoZSAyMCBpcyBhZGRlZCB0byB0aGUgYmFuay48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPiogTGluZSAxOiBUaHJlZSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IFMsIEQsIGFuZCBNPFwvcD5cclxuXHJcbjxwPiogTGluZXMgMi4uUysxOiBMaW5lIHMrMSBjb250YWlucyB0aGUgRCBwcmljZXMgZm9yIHN0b2NrIHMgb24gZGF5cyAxLi5EOiBQUl9zZDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiogTGluZSAxOiBUaGUgbWF4aW11bSBhbW91bnQgb2YgbW9uZXkgcG9zc2libGUgdG8gaGF2ZSBhZnRlciBzZWxsaW5nIG9uIGRheSBELjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > USA Computing Olympiad > 2008-2009 Season > USACO February 2009 Contest > Gold 2번

  • 문제를 번역한 사람: author6
  • 문제의 오타를 찾은 사람: jjwdi0