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

문제

드래곤 나라에는 N개의 도시와 M개의 도로가 있다. 도시들은 1번 부터 N번까지 번호가 붙어 있으며 각 도로는 두개의 도시를 연결한다. 이 N개의 도시에는 전체 합이 K마리인 D1, D2, ... DK드래곤이 살고 있다. 도시 Ci에 살고 있는 드래곤 Di는 처음에 Si의 머리를 가지고 있다. 드래곤이 살아있는 동안 매 분 Ni개의 새로운 머리가 자란다. 드래곤은 하나 이상의 머리가 남아 있으면 생존할 수 있다.

우린 드래곤을 처치하기 위해 워리어를 고용할것이다. 매 분마다 각 워리어는 인접한 도시로 이동하거나 자신이 머물고 있는 도시의 드래곤의 머리 하나를 자를 수 있다. 우리는 워리어가 매 분마다 취할 전략을 정할 수 있다. 또한 우리는 각 워리어가 머무는 최초 도시를 지정할 수 있다.

유한한 시간에 모든 드래곤을 죽이기 위해 필요한 최소 워리어 수를 구하라.

입력

여러 개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 세개의 정수 N, M, K (1 ≤ N ≤ 300, 0 ≤ M ≤ N(N-1), 1 ≤ K ≤ 1000)가 주어진다. 그 후 M개의 줄이 주어진다. 각 줄에는 도시 a와 b 사이의 연결을 가리키는 두개의 정수 a, b (1 ≤ a ≠ b ≤ N)가 주어진다. 이후 K개의 줄이 주어진다. K개 줄의 i번째 줄에는 드래곤 Di에 대한 값 Ci, Si, Ni (1 ≤ Ci ≤ N, 1 ≤ Si ≤ 105, 0 ≤ Ni ≤ 105)이 주어진다. 0 0 0이 입력되면 테스트 케이스는 종료된다.

출력

각 테스트 케이스에 대해 결과는 모든 드래곤을 죽일 수 잇는 최소 워리어 수를 출력해야한다.

예제 입력 1

2 1 1
1 2
1 7 4
4 4 2
1 2
2 4
4 1
1 3
1 2 3
2 3 1
0 0 0

예제 출력 1

5
2
W3sicHJvYmxlbV9pZCI6IjEwNjA1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViNGRjXHViNzk4XHVhY2U0IFx1YzhmZFx1Yzc3NFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHViNGRjXHViNzk4XHVhY2U0IFx1YjA5OFx1Yjc3Y1x1YzVkMFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YjNjNFx1YzJkY1x1YzY0MCBNXHVhYzFjXHVjNzU4IFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YjNjNFx1YzJkY1x1YjRlNFx1Yzc0MCAxXHViYzg4IFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkOTlcdWM1YjQgXHVjNzg4XHVjNzNjXHViYTcwIFx1YWMwMSBcdWIzYzRcdWI4NWNcdWIyOTQgXHViNDUwXHVhYzFjXHVjNzU4IFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBOXHVhYzFjXHVjNzU4IFx1YjNjNFx1YzJkY1x1YzVkMFx1YjI5NCBcdWM4MDRcdWNjYjQgXHVkNTY5XHVjNzc0IEtcdWI5YzhcdWI5YWNcdWM3NzggRDxzdWI+MTxcL3N1Yj4sIEQ8c3ViPjI8XC9zdWI+LCAuLi4gRDxzdWI+SzxcL3N1Yj5cdWI0ZGNcdWI3OThcdWFjZTRcdWM3NzQgXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViM2M0XHVjMmRjIEM8c3ViPmk8XC9zdWI+XHVjNWQwIFx1YzBiNFx1YWNlMCBcdWM3ODhcdWIyOTQgXHViNGRjXHViNzk4XHVhY2U0IEQ8c3ViPmk8XC9zdWI+XHViMjk0IFx1Y2M5OFx1Yzc0Y1x1YzVkMCBTPHN1Yj5pPFwvc3ViPlx1Yzc1OCBcdWJhMzhcdWI5YWNcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViNGRjXHViNzk4XHVhY2U0XHVjNzc0IFx1YzBiNFx1YzU0NFx1Yzc4OFx1YjI5NCBcdWIzZDlcdWM1NDggXHViOWU0IFx1YmQ4NCBOPHN1Yj5pPFwvc3ViPlx1YWMxY1x1Yzc1OCBcdWMwYzhcdWI4NWNcdWM2YjQgXHViYTM4XHViOWFjXHVhYzAwIFx1Yzc5MFx1Yjc4MFx1YjJlNC4gXHViNGRjXHViNzk4XHVhY2U0XHVjNzQwIFx1ZDU1OFx1YjA5OCBcdWM3NzRcdWMwYzFcdWM3NTggXHViYTM4XHViOWFjXHVhYzAwIFx1YjBhOFx1YzU0NCBcdWM3ODhcdWM3M2NcdWJhNzQgXHVjMGRkXHVjODc0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzZiMFx1YjliMCBcdWI0ZGNcdWI3OThcdWFjZTRcdWM3NDQgXHVjYzk4XHVjZTU4XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWM2Y2NcdWI5YWNcdWM1YjRcdWI5N2MgXHVhY2UwXHVjNmE5XHVkNTYwXHVhYzgzXHVjNzc0XHViMmU0LiBcdWI5ZTQgXHViZDg0XHViOWM4XHViMmU0IFx1YWMwMSBcdWM2Y2NcdWI5YWNcdWM1YjRcdWIyOTQgXHVjNzc4XHVjODExXHVkNTVjIFx1YjNjNFx1YzJkY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWFjNzBcdWIwOTggXHVjNzkwXHVjMmUwXHVjNzc0IFx1YmEzOFx1YmIzY1x1YWNlMCBcdWM3ODhcdWIyOTQgXHViM2M0XHVjMmRjXHVjNzU4IFx1YjRkY1x1Yjc5OFx1YWNlNFx1Yzc1OCBcdWJhMzhcdWI5YWMgXHVkNTU4XHViMDk4XHViOTdjIFx1Yzc5MFx1Yjk3YyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM2YjBcdWI5YWNcdWIyOTQgXHVjNmNjXHViOWFjXHVjNWI0XHVhYzAwIFx1YjllNCBcdWJkODRcdWI5YzhcdWIyZTQgXHVjZGU4XHVkNTYwIFx1YzgwNFx1YjdiNVx1Yzc0NCBcdWM4MTVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNjEwXHVkNTVjIFx1YzZiMFx1YjlhY1x1YjI5NCBcdWFjMDEgXHVjNmNjXHViOWFjXHVjNWI0XHVhYzAwIFx1YmEzOFx1YmIzNFx1YjI5NCBcdWNkNWNcdWNkMDggXHViM2M0XHVjMmRjXHViOTdjIFx1YzljMFx1YzgxNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3MjBcdWQ1NWNcdWQ1NWMgXHVjMmRjXHVhYzA0XHVjNWQwIFx1YmFhOFx1YjRlMCBcdWI0ZGNcdWI3OThcdWFjZTRcdWM3NDQgXHVjOGZkXHVjNzc0XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1YzZjY1x1YjlhY1x1YzViNCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMTM4XHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBOLCBNLCBLICgxJm5ic3A7JmxlOyBOICZsZTsgMzAwLCAwICZsZTsgTSAmbGU7IE4oTi0xKSwgMSAmbGU7IEsgJmxlOyAxMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOCBcdWQ2YzQgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjNjNFx1YzJkYyBhXHVjNjQwIGIgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YzVmMFx1YWNiMFx1Yzc0NCBcdWFjMDBcdWI5YWNcdWQwYTRcdWIyOTQgXHViNDUwXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBhLCBiICgxICZsZTsgYSAmbmU7IGIgJmxlOyBOKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1ZDZjNCBLXHVhYzFjXHVjNzU4IFx1YzkwNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIEtcdWFjMWMgXHVjOTA0XHVjNzU4IGlcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjRkY1x1Yjc5OFx1YWNlNCBEPHN1Yj5pPFwvc3ViPlx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVhYzEyIEM8c3ViPmk8XC9zdWI+LCBTPHN1Yj5pPFwvc3ViPiwgTjxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBDPHN1Yj5pPFwvc3ViPiAmbGU7IE4sIDEgJmxlOyBTPHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD41PFwvc3VwPiwgMCAmbGU7IE48c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjU8XC9zdXA+KVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIDAgMCAwXHVjNzc0IFx1Yzc4NVx1YjgyNVx1YjQxOFx1YmE3NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1Yzg4NVx1YjhjY1x1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVhY2IwXHVhY2ZjXHViMjk0IFx1YmFhOFx1YjRlMCBcdWI0ZGNcdWI3OThcdWFjZTRcdWM3NDQgXHVjOGZkXHVjNzdjIFx1YzIxOCBcdWM3ODdcdWIyOTQgXHVjZDVjXHVjMThjIFx1YzZjY1x1YjlhY1x1YzViNCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjEwNjA1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRHJhZ29ucyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlcmUgYXJlIE4gY2l0aWVzIGFuZCBNIHJvYWRzIGluIERyYWdvbnMgQ291bnRyeS4gQ2l0aWVzIGFyZSBudW1iZXJlZCAxIHRocm91Z2ggTiwgYW5kIGVhY2ggcm9hZCBjb25uZWN0cyBleGFjdGx5IHR3byBjaXRpZXMuIFRoZXJlIGFyZSB0b3RhbGx5IEsgZHJhZ29ucyBEMSwgRDIsIC4gLiAuICwgREsgaW4gdGhlc2UgTiBjaXRpZXMuIERyYWdvbiBEaSBsaXZlcyBpbiBjaXR5IENpIGFuZCBoYXMgaW5pdGlhbGx5IFNpIGhlYWRzLiBJdCBncm93cyBOaSBuZXcgaGVhZHMgZXZlcnkgbWludXRlIHdoaWxlIGFsaXZlISBBIGRyYWdvbiBpcyBhbGl2ZSBpZiBpdCBoYXMgcG9zaXRpdmUgbnVtYmVyIG9mIGhlYWRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5XZSB3YW50IHRvIGhpcmUgYSBudW1iZXIgb2Ygd2FycmlvcnMgdG8ga2lsbCBhbGwgZHJhZ29ucy4gV2Ugc3BlY2lmeSB0aGUgaW5pdGlhbCBjaXR5IG9mIGVhY2ggd2Fycmlvci4gVGhlbiBvbiBlYWNoIG1pbnV0ZSwgZWFjaCB3YXJyaW9yIGNhbiBlaXRoZXIgZ28gdGhyb3VnaCBhIHJvYWQgZnJvbSBoaXMgY3VycmVudCBjaXR5IHRvIGFuIGFkamFjZW50IGNpdHksIG9yIHNlbGVjdCBhbiBhbGl2ZSBkcmFnb24gaW4gaGlzIGN1cnJlbnQgY2l0eSBhbmQgY3V0IG9mZiBvbmUgb2YgaXRzIGhlYWRzLiBXZSBjYW4gc3BlY2lmeSB0aGUgc3RyYXRlZ3kgb2YgZWFjaCB3YXJyaW9yIG9uIGVhY2ggbWludXRlLCBhbmQgYWZ0ZXIgdGhleSBhcmUgZG9uZSwgYW55IGFsaXZlIGRyYWdvbiBEaSB3aWxsIGdyb3cgaXRzIE5pIG5ldyBoZWFkcy48XC9wPlxyXG5cclxuPHA+V2Ugd2FudCB0byBmaW5kIHRoZSBtaW5pbXVtIG51bWJlciBvZiB3YXJyaW9ycyB3aXRoIHdoaWNoIGFsbCBkcmFnb25zIGNhbiBiZSBraWxsZWQgaW4gYSBmaW5pdGUgYW1vdW50IG9mIHRpbWUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGVyZSBhcmUgbXVsdGlwbGUgdGVzdCBjYXNlcyBpbiB0aGUgaW5wdXQuIEZvciBlYWNoIHRlc3QgY2FzZSwgdGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhyZWUgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIE4sIE0gYW5kIEsgKDEgXHUyYTdkIE4gXHUyYTdkIDMwMCwgMCBcdTJhN2QgTSBcdTJhN2QgTihOICZtaW51czsgMSlcLzIsIGFuZCAxIFx1MmE3ZCBLIFx1MmE3ZCAxMDAwKS4gRWFjaCBvZiB0aGUgbmV4dCBNIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBhIGFuZCBiICgxIFx1MmE3ZCBhICZuZTsmbmJzcDtiIFx1MmE3ZCBOKSBpbmRpY2F0aW5nIGEgcm9hZCBiZXR3ZWVuIGNpdGllcyBhIGFuZCBiLiBUaGUgaS10aCBsaW5lIG9mIHRoZSBuZXh0IEsgbGluZXMgZGVzY3JpYmVzIGRyYWdvbiBEaSB3aXRoIHRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyBDaSwgU2kgYW5kIE5pICgxIFx1MmE3ZCBDaSBcdTJhN2QgTiwgMSBcdTJhN2QgU2kgXHUyYTdkIDEwPHN1cD41PFwvc3VwPiwgMCBcdTJhN2QgTmkgXHUyYTdkIDEwPHN1cD41PFwvc3VwPikuIFRoZSBpbnB1dCB0ZXJtaW5hdGVzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgMCAwIDAgd2hpY2ggc2hvdWxkIG5vdCBiZSBwcm9jZXNzZWQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgYSBsaW5lIGNvbnRhaW5pbmcgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHdhcnJpb3JzIHdobyBjYW4gZXZlbnR1YWxseSBraWxsIGFsbCBkcmFnb25zLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Asia West Continent > Iran > Tehran Site 2014 G번