시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 6 4 4 100.000%

문제

월드 방송국에서 유선으로 방송을 하고자 한다. 방송망의 형태는 방송국이 루트인 트리의 형태가 될 것이다. 트리의 터미널 노드들은 사용자를 의미하며 트리에서 터미널을 제외한 노드는 송신기 역할을 하게 된다. (루트는 방송국이면서 송신기이며, 루트와 터미널이 아닌 노드들은 중간 송신기라고 불려진다)

한 노드에서 다른 노드로 방송 라인을 설치할 때 드는 비용이 주어진다. 총 방송 비용이란 설치한 방송 라인의 비용을 모두 더한 값이다.

같은 방송망에 있지만 각각의 사용자가 내는 돈은 다를 수 있으며 각각 사용자가 방송을 보게 될 때 지불할 돈이 미리 주어진다.

방송국에서는 방송 라인을 하나 설치할 때 지출을 하게 된다. 또한 방송망이 방송국에서 사용자까지 도달되면 방송국은 그 사용자에게서 시청료를 받게 된다.

방송라인을 적절히 설치해서 방송국이 손해를 보지 않으면서 방송을 해줄 수 있는 최대 사용자는 몇 명인가? (손해를 보지 않는다는 말은 총 시청료 - 총 방송 비용 ≥ 0 임을 의미한다)

입력

첫 줄에 N M이 입력된다. (2 ≤ N ≤ 3,000, 1 ≤ M ≤ N-1)
N은 트리의 노드 개수이고 M은 트리의 터미널 노드 개수이다.
노드의 번호는 트리의 루트가 1이며, 루트가 아닌 다른 송신기들은 2부터 N-M까지, 사용자들(터미널노드들)의 번호는 N-M+1부터 N까지 이다.
두 번째 줄부터 N-M개의 줄에 다음과 같은 형식으로 송신기 정보가 주어진다.
K A1 C1 A2 C2 ... Ak Ck
K는 그 송신기가 송신하는 노드의 개수이며 A는 그 노드의 이름 C는 그 비용을 의미한다.
그 이후의 M개의 라인에는 M명의 사용자의 시청료가 각각 입력된다.

출력

최대 사용자 수를 출력한다.

예제 입력 1

5 3
2 2 2 5 3
2 3 2 4 3
3 4 2

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjE4MTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMjlcdWMxYTFcdWFkNmQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzZkNFx1YjRkYyBcdWJjMjlcdWMxYTFcdWFkNmRcdWM1ZDBcdWMxMWMgXHVjNzIwXHVjMTIwXHVjNzNjXHViODVjIFx1YmMyOVx1YzFhMVx1Yzc0NCBcdWQ1NThcdWFjZTBcdWM3OTAgXHVkNTVjXHViMmU0LiBcdWJjMjlcdWMxYTFcdWI5ZGRcdWM3NTggXHVkNjE1XHVkMGRjXHViMjk0IFx1YmMyOVx1YzFhMVx1YWQ2ZFx1Yzc3NCBcdWI4ZThcdWQyYjhcdWM3NzggXHVkMmI4XHViOWFjXHVjNzU4IFx1ZDYxNVx1ZDBkY1x1YWMwMCBcdWI0MjAgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWQyYjhcdWI5YWNcdWM3NTggXHVkMTMwXHViYmY4XHViMTEwIFx1YjE3OFx1YjRkY1x1YjRlNFx1Yzc0MCBcdWMwYWNcdWM2YTlcdWM3OTBcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTU4XHViYTcwIFx1ZDJiOFx1YjlhY1x1YzVkMFx1YzExYyBcdWQxMzBcdWJiZjhcdWIxMTBcdWM3NDQgXHVjODFjXHVjNjc4XHVkNTVjIFx1YjE3OFx1YjRkY1x1YjI5NCBcdWMxYTFcdWMyZTBcdWFlMzAgXHVjNWVkXHVkNTYwXHVjNzQ0IFx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuIChcdWI4ZThcdWQyYjhcdWIyOTQgXHViYzI5XHVjMWExXHVhZDZkXHVjNzc0XHViYTc0XHVjMTFjIFx1YzFhMVx1YzJlMFx1YWUzMFx1Yzc3NFx1YmE3MCwgXHViOGU4XHVkMmI4XHVjNjQwIFx1ZDEzMFx1YmJmOFx1YjExMFx1Yzc3NCBcdWM1NDRcdWIyY2MgXHViMTc4XHViNGRjXHViNGU0XHVjNzQwIFx1YzkxMVx1YWMwNCBcdWMxYTFcdWMyZTBcdWFlMzBcdWI3N2NcdWFjZTAgXHViZDg4XHViODI0XHVjOWM0XHViMmU0KSA8YnIgXC8+XHJcbjxiciBcLz5cclxuXHVkNTVjIFx1YjE3OFx1YjRkY1x1YzVkMFx1YzExYyBcdWIyZTRcdWI5NzggXHViMTc4XHViNGRjXHViODVjIFx1YmMyOVx1YzFhMSBcdWI3N2NcdWM3NzhcdWM3NDQgXHVjMTI0XHVjZTU4XHVkNTYwIFx1YjU0YyBcdWI0ZGNcdWIyOTQgXHViZTQ0XHVjNmE5XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjZDFkIFx1YmMyOVx1YzFhMSBcdWJlNDRcdWM2YTlcdWM3NzRcdWI3ODAgXHVjMTI0XHVjZTU4XHVkNTVjIFx1YmMyOVx1YzFhMSBcdWI3N2NcdWM3NzhcdWM3NTggXHViZTQ0XHVjNmE5XHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWIzNTRcdWQ1NWMgXHVhYzEyXHVjNzc0XHViMmU0LjxiciBcLz5cclxuPGJyIFwvPlxyXG5cdWFjMTlcdWM3NDAgXHViYzI5XHVjMWExXHViOWRkXHVjNWQwIFx1Yzc4OFx1YzljMFx1YjljYyBcdWFjMDFcdWFjMDFcdWM3NTggXHVjMGFjXHVjNmE5XHVjNzkwXHVhYzAwIFx1YjBiNFx1YjI5NCBcdWIzYzhcdWM3NDAgXHViMmU0XHViOTdjIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAgXHVhYzAxXHVhYzAxIFx1YzBhY1x1YzZhOVx1Yzc5MFx1YWMwMCBcdWJjMjlcdWMxYTFcdWM3NDQgXHViY2Y0XHVhYzhjIFx1YjQyMCBcdWI1NGMgXHVjOWMwXHViZDg4XHVkNTYwIFx1YjNjOFx1Yzc3NCBcdWJiZjhcdWI5YWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxiciBcLz5cclxuPGJyIFwvPlxyXG5cdWJjMjlcdWMxYTFcdWFkNmRcdWM1ZDBcdWMxMWNcdWIyOTQgXHViYzI5XHVjMWExIFx1Yjc3Y1x1Yzc3OFx1Yzc0NCBcdWQ1NThcdWIwOTggXHVjMTI0XHVjZTU4XHVkNTYwIFx1YjU0YyBcdWM5YzBcdWNkOWNcdWM3NDQgXHVkNTU4XHVhYzhjIFx1YjQxY1x1YjJlNC4gXHViNjEwXHVkNTVjIFx1YmMyOVx1YzFhMVx1YjlkZFx1Yzc3NCBcdWJjMjlcdWMxYTFcdWFkNmRcdWM1ZDBcdWMxMWMgXHVjMGFjXHVjNmE5XHVjNzkwXHVhZTRjXHVjOWMwIFx1YjNjNFx1YjJlY1x1YjQxOFx1YmE3NCBcdWJjMjlcdWMxYTFcdWFkNmRcdWM3NDAgXHVhZGY4IFx1YzBhY1x1YzZhOVx1Yzc5MFx1YzVkMFx1YWM4Y1x1YzExYyBcdWMyZGNcdWNjYWRcdWI4Y2NcdWI5N2MgXHViYzFiXHVhYzhjIFx1YjQxY1x1YjJlNC48YnIgXC8+XHJcbjxiciBcLz5cclxuXHViYzI5XHVjMWExXHViNzdjXHVjNzc4XHVjNzQ0IFx1YzgwMVx1YzgwOFx1ZDc4OCBcdWMxMjRcdWNlNThcdWQ1NzRcdWMxMWMgXHViYzI5XHVjMWExXHVhZDZkXHVjNzc0IFx1YzE5MFx1ZDU3NFx1Yjk3YyBcdWJjZjRcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTc0XHVjMTFjIFx1YmMyOVx1YzFhMVx1Yzc0NCBcdWQ1NzRcdWM5MDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVjMGFjXHVjNmE5XHVjNzkwXHViMjk0IFx1YmE4NyBcdWJhODVcdWM3NzhcdWFjMDA/IChcdWMxOTBcdWQ1NzRcdWI5N2MgXHViY2Y0XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNFx1YjI5NCBcdWI5ZDBcdWM3NDAgXHVjZDFkIFx1YzJkY1x1Y2NhZFx1YjhjYyAtIFx1Y2QxZCBcdWJjMjlcdWMxYTEgXHViZTQ0XHVjNmE5ICZnZTsgMCBcdWM3ODRcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0KSIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBOIE1cdWM3NzQgXHVjNzg1XHViODI1XHViNDFjXHViMmU0LiAoMiAmbGU7IE4gJmxlOyAzLDAwMCwgMSAmbGU7IE0gJmxlOyBOLTEpPGJyIFwvPlxyXG5OXHVjNzQwIFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWIxNzhcdWI0ZGMgXHVhYzFjXHVjMjE4XHVjNzc0XHVhY2UwIE1cdWM3NDAgXHVkMmI4XHViOWFjXHVjNzU4IFx1ZDEzMFx1YmJmOFx1YjExMCBcdWIxNzhcdWI0ZGMgXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LjxiciBcLz5cclxuXHViMTc4XHViNGRjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjI5NCBcdWQyYjhcdWI5YWNcdWM3NTggXHViOGU4XHVkMmI4XHVhYzAwIDFcdWM3NzRcdWJhNzAsIFx1YjhlOFx1ZDJiOFx1YWMwMCBcdWM1NDRcdWIyY2MgXHViMmU0XHViOTc4IFx1YzFhMVx1YzJlMFx1YWUzMFx1YjRlNFx1Yzc0MCAyXHViZDgwXHVkMTMwIE4tTVx1YWU0Y1x1YzljMCwgXHVjMGFjXHVjNmE5XHVjNzkwXHViNGU0KFx1ZDEzMFx1YmJmOFx1YjExMFx1YjE3OFx1YjRkY1x1YjRlNClcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IE4tTSsxXHViZDgwXHVkMTMwIE5cdWFlNGNcdWM5YzAgXHVjNzc0XHViMmU0LjxiciBcLz5cclxuXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTi1NXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1ZDYxNVx1YzJkZFx1YzczY1x1Yjg1YyBcdWMxYTFcdWMyZTBcdWFlMzAgXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48YnIgXC8+XHJcbksgQTEgQzEgQTIgQzIgLi4uIEFrIENrPGJyIFwvPlxyXG5LXHViMjk0IFx1YWRmOCBcdWMxYTFcdWMyZTBcdWFlMzBcdWFjMDAgXHVjMWExXHVjMmUwXHVkNTU4XHViMjk0IFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWJhNzAgQVx1YjI5NCBcdWFkZjggXHViMTc4XHViNGRjXHVjNzU4IFx1Yzc3NFx1Yjk4NCBDXHViMjk0IFx1YWRmOCBcdWJlNDRcdWM2YTlcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxiciBcLz5cclxuXHVhZGY4IFx1Yzc3NFx1ZDZjNFx1Yzc1OCBNXHVhYzFjXHVjNzU4IFx1Yjc3Y1x1Yzc3OFx1YzVkMFx1YjI5NCBNXHViYTg1XHVjNzU4IFx1YzBhY1x1YzZhOVx1Yzc5MFx1Yzc1OCBcdWMyZGNcdWNjYWRcdWI4Y2NcdWFjMDAgXHVhYzAxXHVhYzAxIFx1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC4iLCJvdXRwdXQiOiI8cD5cdWNkNWNcdWIzMDAgXHVjMGFjXHVjNmE5XHVjNzkwIFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTgxNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRlbGVwaG9uZSBMaW5lcyIsImRlc2NyaXB0aW9uIjoiPHA+QSBUVi1uZXR3b3JrIHBsYW5zIHRvIGJyb2FkY2FzdCBhbiBpbXBvcnRhbnQgZm9vdGJhbGwgbWF0Y2guIFRoZWlyIG5ldHdvcmsgb2YgdHJhbnNtaXR0ZXJzIGFuZCB1c2VycyBjYW4gYmUgcmVwcmVzZW50ZWQgYXMgYSB0cmVlLiBUaGUgcm9vdCBvZiB0aGUgdHJlZSBpcyBhIHRyYW5zbWl0dGVyIHRoYXQgZW1pdHMgdGhlIGZvb3RiYWxsIG1hdGNoLCB0aGUgbGVhdmVzIG9mIHRoZSB0cmVlIGFyZSB0aGUgcG90ZW50aWFsIHVzZXJzIGFuZCBvdGhlciB2ZXJ0aWNlcyBpbiB0aGUgdHJlZSBhcmUgcmVsYXlzICh0cmFuc21pdHRlcnMpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgcHJpY2Ugb2YgdHJhbnNtaXNzaW9uIG9mIGEgc2lnbmFsIGZyb20gb25lIHRyYW5zbWl0dGVyIHRvIGFub3RoZXIgb3IgdG8gdGhlIHVzZXIgaXMgZ2l2ZW4uIEEgcHJpY2Ugb2YgdGhlIGVudGlyZSBicm9hZGNhc3QgaXMgdGhlIHN1bSBvZiBwcmljZXMgb2YgYWxsIGluZGl2aWR1YWwgc2lnbmFsIHRyYW5zbWlzc2lvbnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkV2ZXJ5IHVzZXIgaXMgcmVhZHkgdG8gcGF5IGEgY2VydGFpbiBhbW91bnQgb2YgbW9uZXkgdG8gd2F0Y2ggdGhlIG1hdGNoIGFuZCB0aGUgVFYtbmV0d29yayB0aGVuIGRlY2lkZXMgd2hldGhlciBvciBub3QgdG8gcHJvdmlkZSB0aGUgdXNlciB3aXRoIHRoZSBzaWduYWwuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgZmluZCB0aGUgbWF4aW1hbCBudW1iZXIgb2YgdXNlcnMgYWJsZSB0byB3YXRjaCB0aGUgbWF0Y2ggc28gdGhhdCB0aGUgVFZuZXR3b3JrJnJzcXVvO3MgZG9lc24mcnNxdW87dCBsb3NlIG1vbmV5IGZyb20gYnJvYWRjYXN0aW5nIHRoZSBtYXRjaC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBmaWxlIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOIGFuZCBNLCAyICZsZTsgTiAmbGU7IDMwMDAsIDEgJmxlOyBNICZsZTsgTi0xLCB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIGluIHRoZSB0cmVlIGFuZCB0aGUgbnVtYmVyIG9mIHBvdGVudGlhbCB1c2Vycy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHJvb3Qgb2YgdGhlIHRyZWUgaXMgbWFya2VkIHdpdGggdGhlIG51bWJlciAxLCB3aGlsZSBvdGhlciB0cmFuc21pdHRlcnMgYXJlIG51bWJlcmVkIDIgdG8gTi1NIGFuZCBwb3RlbnRpYWwgdXNlcnMgYXJlIG51bWJlcmVkIE4tTSsxIHRvIE4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgTi1NIGxpbmVzIGNvbnRhaW4gZGF0YSBhYm91dCB0aGUgdHJhbnNtaXR0ZXJzIGluIHRoZSBmb2xsb3dpbmcgZm9ybTombmJzcDs8XC9wPlxyXG5cclxuPHA+SyBBPHN1Yj4xPFwvc3ViPiBDPHN1Yj4xPFwvc3ViPiBBPHN1Yj4yPFwvc3ViPiBDPHN1Yj4yPFwvc3ViPiAuLi4gQTxzdWI+SzxcL3N1Yj4gQzxzdWI+SzxcL3N1Yj48XC9wPlxyXG5cclxuPHA+TWVhbnMgdGhhdCBhIHRyYW5zbWl0dGVyIHRyYW5zbWl0cyB0aGUgc2lnbmFsIHRvIEsgdHJhbnNtaXR0ZXJzIG9yIHVzZXJzLCBldmVyeSBvbmUgb2YgdGhlbSBkZXNjcmliZWQgYnkgdGhlIHBhaXIgb2YgbnVtYmVycyBBIGFuZCBDLCB0aGUgdHJhbnNtaXR0ZXIgb3IgdXNlciZyc3F1bztzIG51bWJlciBhbmQgdGhlIGNvc3Qgb2YgdHJhbnNtaXR0aW5nIHRoZSBzaWduYWwgdG8gdGhlbS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGxhc3QgbGluZSBjb250YWlucyB0aGUgZGF0YSBhYm91dCB1c2VycywgY29udGFpbmluZyBNIGludGVnZXJzIHJlcHJlc2VudGluZyByZXNwZWN0aXZlbHkgdGhlIHByaWNlIGV2ZXJ5IG9uZSBvZiB0aGVtIGlzIHdpbGxpbmcgdG8gcGF5IHRvIHdhdGNoIHRoZSBtYXRjaC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIHRoZSBvbmx5IGxpbmUgb2YgdGhlIG91dHB1dCBmaWxlIHNob3VsZCBjb250YWluIHRoZSBtYXhpbWFsIG51bWJlciBvZiB1c2VycyBkZXNjcmliZWQgaW4gdGhlIGFib3ZlIHRleHQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d