시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB33131144.000%

문제

한국과학영재학교 학생들은 주말마다 배달 음식을 시켜 먹곤 한다. 그런데 요즘 배달비가 너무 비싸져서 같이 시키는 학생들이 점점 많아지고 있다.

총 $N$명의 학생들이 각자 $M$개의 가게 중 정확히 한 가게를 선택해서 주문하는데, 같은 가게를 선택한 학생들끼리는 함께 주문하면 배달비를 균등하게 나눠서 낼 수 있다. $j$번째 가게에서 음식을 주문한다면 총 $c_j$의 배달비가 발생하는데, 그 가게에서 주문한 학생들이 배달비를 균등하게 나눠서 내게 된다. 각자가 낼 배달비가 꼭 정수일 필요는 없다. $i$번째 학생은 $j$번째 가게에서 주문할 때 자신이 내야 할 배달비가 $r_{i,j}$ 이하일 때 $j$번째 가게에서 음식을 주문할 수 있다.

도영이는 모든 학생이 내는 배달비의 총합을 최소화하게끔 각 학생이 어느 가게에서 음식을 주문할지를 결정하려고 한다. 학생들이 내야 할 배달비 총합의 최솟값을 구해 주자.

입력

첫 번째 줄에 두 정수 $N$과 $M$이 공백을 사이에 두고 주어진다.

두 번째 줄에 $M$개의 정수 $c_1, c_2, \cdots, c_M$이 공백을 사이에 두고 주어진다.

다음 $N$개의 줄에 $r_{i,j}$가 주어지며, 그 중 $i$번째 줄에 $M$개의 정수 $r_{i,1}, r_{i,2}, \cdots, r_{i,M}$이 공백을 사이에 두고 주어진다.

출력

배달비의 총합의 최솟값을 출력한다. 모든 학생이 빠짐없이 배달 음식을 주문하는 것이 불가능하다면 대신 -1을 출력한다.

제한

  • $1 \leq N \leq 15$
  • $1 \leq M \leq 1000$
  • $1 \leq c_j \leq 10^7$
  • $0 \leq r_{i,j} \leq 10^7$

예제 입력 1

3 3
3 2 10
2 0 4
2 0 4
0 2 4

예제 출력 1

5

예제 입력 2

3 3
3 2 10
2 0 4
1 0 4
0 2 4

예제 출력 2

10

예제 입력 3

4 2
8 8
3 2
3 2
3 1
0 2

예제 출력 3

-1
W3sicHJvYmxlbV9pZCI6IjMxOTkyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViYzMwXHViMmVjXHViZTQ0XHVhYzAwIFx1YjEwOFx1YmIzNCBcdWJlNDRcdWMyZjhcdWMxMWMgXHViOWNjXHViNGUwIFx1YmIzOFx1YzgxYyIsImRlc2NyaXB0aW9uIjoiPHA+XHVkNTVjXHVhZDZkXHVhY2ZjXHVkNTU5XHVjNjAxXHVjN2FjXHVkNTU5XHVhZDUwIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCBcdWM4ZmNcdWI5ZDBcdWI5YzhcdWIyZTQgXHViYzMwXHViMmVjIFx1Yzc0Y1x1YzJkZFx1Yzc0NCBcdWMyZGNcdWNmMWMgXHViYTM5XHVhY2U0IFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViN2YwXHViMzcwIFx1YzY5NFx1Yzk5OCBcdWJjMzBcdWIyZWNcdWJlNDRcdWFjMDAgXHViMTA4XHViYjM0IFx1YmU0NFx1YzJmOFx1YzgzOFx1YzExYyBcdWFjMTlcdWM3NzQgXHVjMmRjXHVkMGE0XHViMjk0IFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc3NCBcdWM4MTBcdWM4MTAgXHViOWNlXHVjNTQ0XHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjZDFkICROJFx1YmE4NVx1Yzc1OCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NzQgXHVhYzAxXHVjNzkwICRNJFx1YWMxY1x1Yzc1OCBcdWFjMDBcdWFjOGMgXHVjOTExIFx1YzgxNVx1ZDY1NVx1ZDc4OCBcdWQ1NWMgXHVhYzAwXHVhYzhjXHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU3NFx1YzExYyBcdWM4ZmNcdWJiMzhcdWQ1NThcdWIyOTRcdWIzNzAsIFx1YWMxOVx1Yzc0MCBcdWFjMDBcdWFjOGNcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTVjIFx1ZDU1OVx1YzBkZFx1YjRlNFx1YjA3Y1x1YjlhY1x1YjI5NCBcdWQ1NjhcdWFlZDggXHVjOGZjXHViYjM4XHVkNTU4XHViYTc0IFx1YmMzMFx1YjJlY1x1YmU0NFx1Yjk3YyBcdWFkZTBcdWI0ZjFcdWQ1NThcdWFjOGMgXHViMDk4XHViMjIwXHVjMTFjIFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiAkaiRcdWJjODhcdWM5ZjggXHVhYzAwXHVhYzhjXHVjNWQwXHVjMTFjIFx1Yzc0Y1x1YzJkZFx1Yzc0NCBcdWM4ZmNcdWJiMzhcdWQ1NWNcdWIyZTRcdWJhNzQgXHVjZDFkICRjX2okXHVjNzU4IFx1YmMzMFx1YjJlY1x1YmU0NFx1YWMwMCBcdWJjMWNcdWMwZGRcdWQ1NThcdWIyOTRcdWIzNzAsIFx1YWRmOCBcdWFjMDBcdWFjOGNcdWM1ZDBcdWMxMWMgXHVjOGZjXHViYjM4XHVkNTVjIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc3NCBcdWJjMzBcdWIyZWNcdWJlNDRcdWI5N2MgXHVhZGUwXHViNGYxXHVkNTU4XHVhYzhjIFx1YjA5OFx1YjIyMFx1YzExYyBcdWIwYjRcdWFjOGMgXHViNDFjXHViMmU0LiBcdWFjMDFcdWM3OTBcdWFjMDAgXHViMGJjIFx1YmMzMFx1YjJlY1x1YmU0NFx1YWMwMCBcdWFmMmQgXHVjODE1XHVjMjE4XHVjNzdjIFx1ZDU0NFx1YzY5NFx1YjI5NCBcdWM1YzZcdWIyZTQuICRpJFx1YmM4OFx1YzlmOCBcdWQ1NTlcdWMwZGRcdWM3NDAgJGokXHViYzg4XHVjOWY4IFx1YWMwMFx1YWM4Y1x1YzVkMFx1YzExYyBcdWM4ZmNcdWJiMzhcdWQ1NjAgXHViNTRjIFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWIwYjRcdWM1N2MgXHVkNTYwIFx1YmMzMFx1YjJlY1x1YmU0NFx1YWMwMCAkcl97aSxqfSQgXHVjNzc0XHVkNTU4XHVjNzdjIFx1YjU0YyAkaiRcdWJjODhcdWM5ZjggXHVhYzAwXHVhYzhjXHVjNWQwXHVjMTFjIFx1Yzc0Y1x1YzJkZFx1Yzc0NCBcdWM4ZmNcdWJiMzhcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViM2M0XHVjNjAxXHVjNzc0XHViMjk0IFx1YmFhOFx1YjRlMCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHViMGI0XHViMjk0IFx1YmMzMFx1YjJlY1x1YmU0NFx1Yzc1OCBcdWNkMWRcdWQ1NjlcdWM3NDQgXHVjZDVjXHVjMThjXHVkNjU0XHVkNTU4XHVhYzhjXHViMDU0IFx1YWMwMSBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVjNWI0XHViMjkwIFx1YWMwMFx1YWM4Y1x1YzVkMFx1YzExYyBcdWM3NGNcdWMyZGRcdWM3NDQgXHVjOGZjXHViYjM4XHVkNTYwXHVjOWMwXHViOTdjIFx1YWNiMFx1YzgxNVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc3NCBcdWIwYjRcdWM1N2MgXHVkNTYwIFx1YmMzMFx1YjJlY1x1YmU0NCBcdWNkMWRcdWQ1NjlcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU3NCBcdWM4ZmNcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI0NTAgXHVjODE1XHVjMjE4ICROJFx1YWNmYyAkTSRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0NTBcdWFjZTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCAkTSRcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4ICRjXzEsIGNfMiwgXFxjZG90cywgY19NJFx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyAkTiRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwICRyX3tpLGp9JFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YWRmOCBcdWM5MTEgJGkkXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCAkTSRcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4ICRyX3tpLDF9LCByX3tpLDJ9LCBcXGNkb3RzLCByX3tpLE19JFx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViYzMwXHViMmVjXHViZTQ0XHVjNzU4IFx1Y2QxZFx1ZDU2OVx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWJhYThcdWI0ZTAgXHVkNTU5XHVjMGRkXHVjNzc0IFx1YmU2MFx1YzlkMFx1YzVjNlx1Yzc3NCBcdWJjMzBcdWIyZWMgXHVjNzRjXHVjMmRkXHVjNzQ0IFx1YzhmY1x1YmIzOFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzQgXHViZDg4XHVhYzAwXHViMmE1XHVkNTU4XHViMmU0XHViYTc0IFx1YjMwMFx1YzJlMCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+LTE8XC9jb2RlPjxcL3NwYW4+XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDEgXFxsZXEgTiBcXGxlcSAxNSQ8XC9saT5cclxuXHQ8bGk+JDEgXFxsZXEgTSBcXGxlcSAxMDAwJDxcL2xpPlxyXG5cdDxsaT4kMSBcXGxlcSBjX2ogXFxsZXEgMTBeNyQ8XC9saT5cclxuXHQ8bGk+JDAgXFxsZXEgcl97aSxqfSBcXGxlcSAxMF43JDxcL2xpPlxyXG48XC91bD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMzE5OTIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJEZWxpdmVyeSBGZWVzIGFyZSB0b28gRXhwZW5zaXZlIiwiZGVzY3JpcHRpb24iOiI8cD5TdHVkZW50cyBhdCB0aGUgS29yZWEgU2NpZW5jZSBBY2FkZW15IG9mdGVuIG9yZGVyIGRlbGl2ZXJ5IGZvb2Qgb24gd2Vla2VuZHMuIEhvd2V2ZXIsIHJpc2luZyBkZWxpdmVyeSBmZWVzIGhhdmUgbGVkIHRvIGFuIGluY3JlYXNlIGluIGdyb3VwIG9yZGVycy48XC9wPlxyXG5cclxuPHA+JE4kIHN0dWRlbnRzIGVhY2ggY2hvb3NlIGV4YWN0bHkgb25lIG9mICRNJCByZXN0YXVyYW50cyB0byBwbGFjZSBhbiBvcmRlciwgYW5kIGlmIHNvbWUgc3R1ZGVudHMgY2hvb3NlIHRoZSBzYW1lIHJlc3RhdXJhbnQsIHRoZXkgY2FuIHNoYXJlIHRoZSBkZWxpdmVyeSBmZWUgZXF1YWxseS4gSWYgdGhlICRqJC10aCByZXN0YXVyYW50IGlzIGNob3NlbiwgYSB0b3RhbCBkZWxpdmVyeSBmZWUgb2YgJGNfaiQgd2lsbCBiZSBpbmN1cnJlZC4gVGhlIGRlbGl2ZXJ5IGZlZSBmb3IgZWFjaCByZXN0YXVyYW50IHdpbGwgYmUgZGl2aWRlZCBlcXVhbGx5IGFtb25nIHRoZSBzdHVkZW50cyB3aG8gb3JkZXJlZCBmcm9tIHRoZXJlLCBhbmQgdGhlIGluZGl2aWR1YWwgc2hhcmVzIGRvIG5vdCBuZWVkIHRvIGJlIHdob2xlIG51bWJlcnMuICRpJC10aCBzdHVkZW50IGNhbiBvcmRlciBmb29kIGZyb20gdGhlICRqJC10aCByZXN0YXVyYW50IGlmIHRoZSBkZWxpdmVyeSBmZWUgdGhleSBoYXZlIHRvIHBheSBpcyBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gJHJfe2ksan0kLjxcL3A+XHJcblxyXG48cD5Eb3lvdW5nIHdhbnRzIHRvIGRldGVybWluZSB3aGVyZSBlYWNoIHN0dWRlbnQgd2lsbCBvcmRlciBmb29kIHRvIG1pbmltaXplIHRoZSB0b3RhbCBkZWxpdmVyeSBmZWVzIHBhaWQgYnkgYWxsIHN0dWRlbnRzLiBMZXQmIzM5O3MgZmluZCB0aGUgbWluaW11bSB0b3RhbCBkZWxpdmVyeSBmZWUgdGhhdCBhbGwgc3R1ZGVudHMgaGF2ZSB0byBwYXkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgJE4kIGFuZCAkTSQgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyAkTSQgaW50ZWdlcnMgJGNfMSwgY18yLCBcXGNkb3RzLCBjX00kIHNlcGFyYXRlZCBieSBzcGFjZXMuPFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgJE4kIGxpbmVzIGNvbnRhaW4gJHJfe2ksan0kLCB3aXRoIHRoZSAkaSQtdGggbGluZSBjb250YWluaW5nICRNJCBpbnRlZ2VycyAkcl97aSwxfSwgcl97aSwyfSwgXFxjZG90cywgcl97aSxNfSQgc2VwYXJhdGVkIGJ5IHNwYWNlcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCB0aGUgbWluaW11bSB0b3RhbCBkZWxpdmVyeSBmZWUuIElmIGl0JiMzOTtzIGltcG9zc2libGUgdG8gb3JkZXIgZm9vZCBmb3IgZXZlcnkgc3R1ZGVudCwgcHJpbnQgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPi0xPFwvY29kZT48XC9zcGFuPiZuYnNwO2luc3RlYWQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMSBcXGxlcSZuYnNwO04gXFxsZXEmbmJzcDsxNSQ8XC9saT5cclxuXHQ8bGk+JDEgXFxsZXEmbmJzcDtNIFxcbGVxJm5ic3A7MTAwMCQ8XC9saT5cclxuXHQ8bGk+JDEgXFxsZXEmbmJzcDtjX2ogXFxsZXEmbmJzcDsxMF43JDxcL2xpPlxyXG5cdDxsaT4kMCBcXGxlcSByX3tpLGp9IFxcbGVxJm5ic3A7MTBeNyQ8XC9saT5cclxuPFwvdWw+XHJcbiJ9XQ==

출처

School > 한국과학영재학교 > 2023 Fall Creative Problem Solving D번