시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB147366831502643.815%

문제

수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다.

몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다. 작업들 중에는, 그것에 대해 선행 관계에 있는 작업이 하나도 없는 작업이 반드시 하나 이상 존재한다. (1번 작업이 항상 그러하다)

모든 작업을 완료하기 위해 필요한 최소 시간을 구하여라. 물론, 서로 선행 관계가 없는 작업들은 동시에 수행 가능하다.

입력

첫째 줄에 N이 주어진다.

두 번째 줄부터 N+1번째 줄까지 N개의 줄이 주어진다. 2번째 줄은 1번 작업, 3번째 줄은 2번 작업, ..., N+1번째 줄은 N번 작업을 각각 나타낸다. 각 줄의 처음에는, 해당 작업에 걸리는 시간이 먼저 주어지고, 그 다음에 그 작업에 대해 선행 관계에 있는 작업들의 개수(0 ≤ 개수 ≤ 100)가 주어진다. 그리고 선행 관계에 있는 작업들의 번호가 주어진다.

출력

첫째 줄에 모든 작업을 완료하기 위한 최소 시간을 출력한다.

예제 입력 1

7
5 0
1 1 1
3 1 2
6 1 1
1 2 2 4
8 2 2 4
4 3 3 5 6

예제 출력 1

23

힌트

  • 1번 작업 : 0~5 
  • 2번 작업 : 5~6
  • 3번 작업 : 6~9 
  • 4번 작업 : 5~11
  • 5번 작업 : 11~12
  • 6번 작업 : 11~19
  • 7번 작업 : 19~23
W3sicHJvYmxlbV9pZCI6IjIwNTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3OTFcdWM1YzUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzIxOFx1ZDU4OVx1ZDU3NFx1YzU3YyBcdWQ1NjAgXHVjNzkxXHVjNWM1IE5cdWFjMWMgKDMgJmxlOyZuYnNwO04gJmxlOyZuYnNwOzEwMDAwKVx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM3OTFcdWM1YzVcdWI5YzhcdWIyZTQgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNCgxICZsZTsmbmJzcDtcdWMyZGNcdWFjMDQgJmxlOyAxMDApXHVjNzc0IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmE4N1x1YmE4NyBcdWM3OTFcdWM1YzVcdWI0ZTQgXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1YzEyMFx1ZDU4OSBcdWFkMDBcdWFjYzRcdWI3N2NcdWIyOTQgXHVhYzhjIFx1Yzc4OFx1YzViNFx1YzExYywgXHVjNWI0XHViNWE0IFx1Yzc5MVx1YzVjNVx1Yzc0NCBcdWMyMThcdWQ1ODlcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YmMxOFx1YjRkY1x1YzJkYyBcdWJhM2NcdWM4MDAgXHVjNjQ0XHViOGNjXHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU2MCBcdWM3OTFcdWM1YzVcdWI0ZTRcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVjNzkxXHVjNWM1XHViNGU0XHVjNzQwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWM1NDRcdWM4ZmMgXHVjNjA4XHVjMDU4XHVhYzhjIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWM1YjRcdWMxMWMsIEtcdWJjODggXHVjNzkxXHVjNWM1XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWMxMjBcdWQ1ODkgXHVhZDAwXHVhY2M0XHVjNWQwIFx1Yzc4OFx1YjI5NChcdWM5ODksIEtcdWJjODggXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YWUzMCBcdWM4MDRcdWM1ZDAgXHViYzE4XHViNGRjXHVjMmRjIFx1YmEzY1x1YzgwMCBcdWM2NDRcdWI4Y2NcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTU4XHViMjk0KSBcdWM3OTFcdWM1YzVcdWI0ZTRcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IFx1YmFhOFx1YjQ1MCAxIFx1Yzc3NFx1YzBjMSAoSy0xKSBcdWM3NzRcdWQ1NThcdWM3NzRcdWIyZTQuIFx1Yzc5MVx1YzVjNVx1YjRlNCBcdWM5MTFcdWM1ZDBcdWIyOTQsIFx1YWRmOFx1YWM4M1x1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjMTIwXHVkNTg5IFx1YWQwMFx1YWNjNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjNzkxXHVjNWM1XHVjNzc0IFx1ZDU1OFx1YjA5OFx1YjNjNCBcdWM1YzZcdWIyOTQgXHVjNzkxXHVjNWM1XHVjNzc0IFx1YmMxOFx1YjRkY1x1YzJkYyBcdWQ1NThcdWIwOTggXHVjNzc0XHVjMGMxIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC4gKDFcdWJjODggXHVjNzkxXHVjNWM1XHVjNzc0IFx1ZDU2ZFx1YzBjMSBcdWFkZjhcdWI3ZWNcdWQ1NThcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWM3OTFcdWM1YzVcdWM3NDQgXHVjNjQ0XHViOGNjXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWFkNmNcdWQ1NThcdWM1ZWNcdWI3N2MuIFx1YmIzY1x1Yjg2MCwgXHVjMTFjXHViODVjIFx1YzEyMFx1ZDU4OSBcdWFkMDBcdWFjYzRcdWFjMDAgXHVjNWM2XHViMjk0IFx1Yzc5MVx1YzVjNVx1YjRlNFx1Yzc0MCBcdWIzZDlcdWMyZGNcdWM1ZDAgXHVjMjE4XHVkNTg5IFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE4rMVx1YmM4OFx1YzlmOCBcdWM5MDRcdWFlNGNcdWM5YzAgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAyXHViYzg4XHVjOWY4IFx1YzkwNFx1Yzc0MCAxXHViYzg4IFx1Yzc5MVx1YzVjNSwgM1x1YmM4OFx1YzlmOCBcdWM5MDRcdWM3NDAgMlx1YmM4OCBcdWM3OTFcdWM1YzUsIC4uLiwgTisxXHViYzg4XHVjOWY4IFx1YzkwNFx1Yzc0MCBOXHViYzg4IFx1Yzc5MVx1YzVjNVx1Yzc0NCBcdWFjMDFcdWFjMDEgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWFjMDEgXHVjOTA0XHVjNzU4IFx1Y2M5OFx1Yzc0Y1x1YzVkMFx1YjI5NCwgXHVkNTc0XHViMmY5IFx1Yzc5MVx1YzVjNVx1YzVkMCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YmEzY1x1YzgwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YWRmOCBcdWIyZTRcdWM3NGNcdWM1ZDAgXHVhZGY4IFx1Yzc5MVx1YzVjNVx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjMTIwXHVkNTg5IFx1YWQwMFx1YWNjNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjNzkxXHVjNWM1XHViNGU0XHVjNzU4IFx1YWMxY1x1YzIxOCgwICZsZTsmbmJzcDtcdWFjMWNcdWMyMTggJmxlOyAxMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YzEyMFx1ZDU4OSBcdWFkMDBcdWFjYzRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1Yzc5MVx1YzVjNVx1YjRlNFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYWE4XHViNGUwIFx1Yzc5MVx1YzVjNVx1Yzc0NCBcdWM2NDRcdWI4Y2NcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8dWw+XHJcblx0PGxpPjFcdWJjODggXHVjNzkxXHVjNWM1IDogMH41Jm5ic3A7PFwvbGk+XHJcblx0PGxpPjJcdWJjODggXHVjNzkxXHVjNWM1IDogNX42PFwvbGk+XHJcblx0PGxpPjNcdWJjODggXHVjNzkxXHVjNWM1IDogNn45Jm5ic3A7PFwvbGk+XHJcblx0PGxpPjRcdWJjODggXHVjNzkxXHVjNWM1IDogNX4xMTxcL2xpPlxyXG5cdDxsaT41XHViYzg4IFx1Yzc5MVx1YzVjNSA6IDExfjEyPFwvbGk+XHJcblx0PGxpPjZcdWJjODggXHVjNzkxXHVjNWM1IDogMTF+MTk8XC9saT5cclxuXHQ8bGk+N1x1YmM4OCBcdWM3OTFcdWM1YzUgOiAxOX4yMzxcL2xpPlxyXG48XC91bD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMDU2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ2hvcmVzIiwiZGVzY3JpcHRpb24iOiI8cD5GYXJtZXIgSm9obiYjMzk7cyBmYW1pbHkgcGl0Y2hlcyBpbiB3aXRoIHRoZSBjaG9yZXMgZHVyaW5nIG1pbGtpbmcsIGRvaW5nIGFsbCB0aGUgY2hvcmVzIGFzIHF1aWNrbHkgYXMgcG9zc2libGUuIEF0IEZKJiMzOTtzIGhvdXNlLCBzb21lIGNob3JlcyBjYW5ub3QgYmUgc3RhcnRlZCB1bnRpbCBvdGhlcnMgaGF2ZSBiZWVuIGNvbXBsZXRlZCwgZS5nLiwgaXQgaXMgaW1wb3NzaWJsZSB0byB3YXNoIHRoZSBjb3dzIHVudGlsIHRoZXkgYXJlIGluIHRoZSBzdGFsbHMuPFwvcD5cclxuXHJcbjxwPkZhcm1lciBKb2huIGhhcyBhIGxpc3Qgb2YgTiAoMyAmbHQ7PSBOICZsdDs9IDEwLDAwMCkgY2hvcmVzIHRoYXQgbXVzdCBiZSBjb21wbGV0ZWQuIEVhY2ggY2hvcmUgcmVxdWlyZXMgYW4gaW50ZWdlciB0aW1lICgxICZsdDs9IGxlbmd0aCBvZiB0aW1lICZsdDs9IDEwMCkgdG8gY29tcGxldGUgYW5kIHRoZXJlIG1heSBiZSBvdGhlciBjaG9yZXMgdGhhdCBtdXN0IGJlIGNvbXBsZXRlZCBiZWZvcmUgdGhpcyBjaG9yZSBpcyBzdGFydGVkLiBXZSB3aWxsIGNhbGwgdGhlc2UgcHJlcmVxdWlzaXRlIGNob3Jlcy4gQXQgbGVhc3Qgb25lIGNob3JlIGhhcyBubyBwcmVyZXF1aXNpdGU6IHRoZSB2ZXJ5IGZpcnN0IG9uZSwgbnVtYmVyIDEuIEZhcm1lciBKb2huJiMzOTtzIGxpc3Qgb2YgY2hvcmVzIGlzIG5pY2VseSBvcmRlcmVkLCBhbmQgY2hvcmUgSyAoSyAmZ3Q7IDEpIGNhbiBoYXZlIG9ubHkgY2hvcmVzIDEsLkstMSBhcyBwcmVyZXF1aXNpdGVzLiBXcml0ZSBhIHByb2dyYW0gdGhhdCByZWFkcyBhIGxpc3Qgb2YgY2hvcmVzIGZyb20gMSB0byBOIHdpdGggYXNzb2NpYXRlZCB0aW1lcyBhbmQgYWxsIHBlcnF1aXNpdGUgY2hvcmVzLiBOb3cgY2FsY3VsYXRlIHRoZSBzaG9ydGVzdCB0aW1lIGl0IHdpbGwgdGFrZSB0byBjb21wbGV0ZSBhbGwgTiBjaG9yZXMuIE9mIGNvdXJzZSwgY2hvcmVzIHRoYXQgZG8gbm90IGRlcGVuZCBvbiBlYWNoIG90aGVyIGNhbiBiZSBwZXJmb3JtZWQgc2ltdWx0YW5lb3VzbHkuPFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogT25lIGludGVnZXIsIE48XC9saT5cclxuXHQ8bGk+TGluZXMgMi4uTisxOiBOIGxpbmVzLCBlYWNoIHdpdGggc2V2ZXJhbCBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMuIExpbmUgMiBjb250YWlucyBjaG9yZSAxOyBsaW5lIDMgY29udGFpbnMgY2hvcmUgMiwgYW5kIHNvIG9uLiBFYWNoIGxpbmUgY29udGFpbnMgdGhlIGxlbmd0aCBvZiB0aW1lIHRvIGNvbXBsZXRlIHRoZSBjaG9yZSwgdGhlIG51bWJlciBvZiB0aGUgcHJlcmVxdWlzaXRlcywgUGksICgwICZsdDs9IFBpICZsdDs9IDEwMCksIGFuZCB0aGUgUGkgcHJlcmVxdWlzaXRlcyAocmFuZ2UgMS4uTiwgb2YgY291cnNlKS48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPkEgc2luZ2xlIGxpbmUgd2l0aCBhbiBpbnRlZ2VyIHdoaWNoIGlzIHRoZSBsZWFzdCBhbW91bnQgb2YgdGltZSByZXF1aXJlZCB0byBwZXJmb3JtIGFsbCB0aGUgY2hvcmVzLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5IZXJlIGlzIG9uZSB0YXNrIHNjaGVkdWxlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkNob3JlIDEgc3RhcnRzIGF0IHRpbWUgMCwgZW5kcyBhdCB0aW1lIDUuPFwvbGk+XHJcblx0PGxpPkNob3JlIDIgc3RhcnRzIGF0IHRpbWUgNSwgZW5kcyBhdCB0aW1lIDYuPFwvbGk+XHJcblx0PGxpPkNob3JlIDMgc3RhcnRzIGF0IHRpbWUgNiwgZW5kcyBhdCB0aW1lIDkuPFwvbGk+XHJcblx0PGxpPkNob3JlIDQgc3RhcnRzIGF0IHRpbWUgNSwgZW5kcyBhdCB0aW1lIDExLjxcL2xpPlxyXG5cdDxsaT5DaG9yZSA1IHN0YXJ0cyBhdCB0aW1lIDExLCBlbmRzIGF0IHRpbWUgMTIuPFwvbGk+XHJcblx0PGxpPkNob3JlIDYgc3RhcnRzIGF0IHRpbWUgMTEsIGVuZHMgYXQgdGltZSAxOS48XC9saT5cclxuXHQ8bGk+Q2hvcmUgNyBzdGFydHMgYXQgdGltZSAxOSwgZW5kcyBhdCB0aW1lIDIzLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > USA Computing Olympiad > 2001-2002 Season > USACO February 2002 Contest > Green or Orange ?번