시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 70 10 8 19.048%

문제

원섭시에는 N명의 시민들이 살고 있다. 이 마을에 살고있는 모든 시민은 각각 다른 시민 1명에게 돈을 빌렸다. 이제 모든 빚을 갚아야하는 시간이다. 그런데, 큰 문제가 생겨서 모든 사람들이 돈을 갚을 수 없게 되었다. 그 이유는 각자 가지고 있는 돈을 모두 써버렸기 때문이다.

원섭시의 시장 고원섭은 이런 악순환을 해결하고자 마을에서 일부 사람들에게 돈을 주기로 했다. 이렇게 일부 사람들이 돈을 받게 되면, 그 돈으로 돈을 갚고, 또 받은 사람은 돈을 갚을 수 있게 된다. 예를 들어, A가 마을에서 돈을 받았다고 하자. 그럼 A는 B에게 돈을 갚을 수 있고, B는 C에게 돈을 갚을 수 있다. 만약, B가 빚을 갚을 수 있는 충분한 돈이 없다면, 충분한 돈이 생길 때 까지 기다리면 된다. 또, B가 돈을 더 가지고 있다면, B는 그 돈을 가지면 된다.

다른 예로, 이 마을에 두 사람이 살고 있고, 두 사람이 서로에게 100원을 빌린 경우를 생각해보자. 이 경우에 마을에서 두 사람 중 한 사람에게 100원을 주면, 서로 빚을 갚을 수 있게 된다.

원섭시의 모든 시민들의 채무 관계가 주어졌을 때, 마을의 악순환을 해결하기 위해 필요한 금액의 최소값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 시민의 수 N (2 ≤ N ≤ 200,000)이 주어진다. 각 사람의 번호는 1번부터 N번이다.

다음 N개의 줄에는 공백으로 구분되어져 있는 두 정수 Ai와 Bi가 주어진다. Ai는 i번 사람이 돈을 빌린 사람의 번호이고, Bi는 갚아야 하는 금액이다. (1 ≤ Ai ≤ N, Ai ≠ i, 1 ≤ Bi ≤ 10,000)

출력

첫째 줄에 시민들의 빚을 해결하기 위해 필요한 최소 금액을 출력한다.

예제 입력 1

4
2 100
1 100
4 70
3 70

예제 출력 1

170

힌트

W3sicHJvYmxlbV9pZCI6IjI4NjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2ZDBcdWMxMmRcdWIzZDkgXHVjMGFjXHViNzhjXHViNGU0IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWM2ZDBcdWMxMmRcdWMyZGNcdWM1ZDBcdWIyOTQgTlx1YmE4NVx1Yzc1OCBcdWMyZGNcdWJiZmNcdWI0ZTRcdWM3NzQgXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YjljOFx1Yzc0NFx1YzVkMCBcdWMwYjRcdWFjZTBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1YzJkY1x1YmJmY1x1Yzc0MCBcdWFjMDFcdWFjMDEgXHViMmU0XHViOTc4IFx1YzJkY1x1YmJmYyAxXHViYTg1XHVjNWQwXHVhYzhjIFx1YjNjOFx1Yzc0NCBcdWJlNGNcdWI4MzhcdWIyZTQuIFx1Yzc3NFx1YzgxYyBcdWJhYThcdWI0ZTAgXHViZTVhXHVjNzQ0IFx1YWMxYVx1YzU0NFx1YzU3Y1x1ZDU1OFx1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NzRcdWIyZTQuIFx1YWRmOFx1YjdmMFx1YjM3MCwgXHVkMDcwIFx1YmIzOFx1YzgxY1x1YWMwMCBcdWMwZGRcdWFjYThcdWMxMWMgXHViYWE4XHViNGUwIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc3NCBcdWIzYzhcdWM3NDQgXHVhYzFhXHVjNzQ0IFx1YzIxOCBcdWM1YzZcdWFjOGMgXHViNDE4XHVjNWM4XHViMmU0LiBcdWFkZjggXHVjNzc0XHVjNzIwXHViMjk0IFx1YWMwMVx1Yzc5MCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YjNjOFx1Yzc0NCBcdWJhYThcdWI0NTAgXHVjMzY4XHViYzg0XHViODM4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNmQwXHVjMTJkXHVjMmRjXHVjNzU4IFx1YzJkY1x1YzdhNSBcdWFjZTBcdWM2ZDBcdWMxMmRcdWM3NDAgXHVjNzc0XHViN2YwIFx1YzU0NVx1YzIxY1x1ZDY1OFx1Yzc0NCBcdWQ1NzRcdWFjYjBcdWQ1NThcdWFjZTBcdWM3OTAgXHViOWM4XHVjNzQ0XHVjNWQwXHVjMTFjIFx1Yzc3Y1x1YmQ4MCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM1ZDBcdWFjOGMgXHViM2M4XHVjNzQ0IFx1YzhmY1x1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWM3N2NcdWJkODAgXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0IFx1YjNjOFx1Yzc0NCBcdWJjMWJcdWFjOGMgXHViNDE4XHViYTc0LCBcdWFkZjggXHViM2M4XHVjNzNjXHViODVjIFx1YjNjOFx1Yzc0NCBcdWFjMWFcdWFjZTAsIFx1YjYxMCBcdWJjMWJcdWM3NDAgXHVjMGFjXHViNzhjXHVjNzQwIFx1YjNjOFx1Yzc0NCBcdWFjMWFcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIEFcdWFjMDAgXHViOWM4XHVjNzQ0XHVjNWQwXHVjMTFjIFx1YjNjOFx1Yzc0NCBcdWJjMWJcdWM1NThcdWIyZTRcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWFkZjhcdWI3ZmMgQVx1YjI5NCBCXHVjNWQwXHVhYzhjIFx1YjNjOFx1Yzc0NCBcdWFjMWFcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgQlx1YjI5NCBDXHVjNWQwXHVhYzhjIFx1YjNjOFx1Yzc0NCBcdWFjMWFcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViOWNjXHVjNTdkLCBCXHVhYzAwIFx1YmU1YVx1Yzc0NCBcdWFjMWFcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkYTlcdWJkODRcdWQ1NWMgXHViM2M4XHVjNzc0IFx1YzVjNlx1YjJlNFx1YmE3NCwgXHVjZGE5XHViZDg0XHVkNTVjIFx1YjNjOFx1Yzc3NCBcdWMwZGRcdWFlMzggXHViNTRjIFx1YWU0Y1x1YzljMCBcdWFlMzBcdWIyZTRcdWI5YWNcdWJhNzQgXHViNDFjXHViMmU0LiBcdWI2MTAsIEJcdWFjMDAgXHViM2M4XHVjNzQ0IFx1YjM1NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0XHViYTc0LCBCXHViMjk0IFx1YWRmOCBcdWIzYzhcdWM3NDQgXHVhYzAwXHVjOWMwXHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU0XHViOTc4IFx1YzYwOFx1Yjg1YywgXHVjNzc0IFx1YjljOFx1Yzc0NFx1YzVkMCBcdWI0NTAgXHVjMGFjXHViNzhjXHVjNzc0IFx1YzBiNFx1YWNlMCBcdWM3ODhcdWFjZTAsIFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjMTFjXHViODVjXHVjNWQwXHVhYzhjIDEwMFx1YzZkMFx1Yzc0NCBcdWJlNGNcdWI5YjAgXHVhY2JkXHVjNmIwXHViOTdjIFx1YzBkZFx1YWMwMVx1ZDU3NFx1YmNmNFx1Yzc5MC4gXHVjNzc0IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWI5YzhcdWM3NDRcdWM1ZDBcdWMxMWMgXHViNDUwIFx1YzBhY1x1Yjc4YyBcdWM5MTEgXHVkNTVjIFx1YzBhY1x1Yjc4Y1x1YzVkMFx1YWM4YyAxMDBcdWM2ZDBcdWM3NDQgXHVjOGZjXHViYTc0LCBcdWMxMWNcdWI4NWMgXHViZTVhXHVjNzQ0IFx1YWMxYVx1Yzc0NCBcdWMyMTggXHVjNzg4XHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNmQwXHVjMTJkXHVjMmRjXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWMyZGNcdWJiZmNcdWI0ZTRcdWM3NTggXHVjYzQ0XHViYjM0IFx1YWQwMFx1YWNjNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWI5YzhcdWM3NDRcdWM3NTggXHVjNTQ1XHVjMjFjXHVkNjU4XHVjNzQ0IFx1ZDU3NFx1YWNiMFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YWUwOFx1YzU2MVx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzJkY1x1YmJmY1x1Yzc1OCBcdWMyMTggTiAoMiAmbGU7IE4gJmxlOyAyMDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWMwYWNcdWI3OGNcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IDFcdWJjODhcdWJkODBcdWQxMzAgTlx1YmM4OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjRcdWM4MzggXHVjNzg4XHViMjk0IFx1YjQ1MCBcdWM4MTVcdWMyMTggQTxzdWI+aTxcL3N1Yj5cdWM2NDAgQjxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBBPHN1Yj5pPFwvc3ViPlx1YjI5NCBpXHViYzg4IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWIzYzhcdWM3NDQgXHViZTRjXHViOWIwIFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWJjODhcdWQ2MzhcdWM3NzRcdWFjZTAsIEI8c3ViPmk8XC9zdWI+XHViMjk0IFx1YWMxYVx1YzU0NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVhZTA4XHVjNTYxXHVjNzc0XHViMmU0LiAoMSAmbGU7IEE8c3ViPmk8XC9zdWI+ICZsZTsgTiwgQTxzdWI+aTxcL3N1Yj4gJm5lOyBpLCAxICZsZTsgQjxzdWI+aTxcL3N1Yj4gJmxlOyAxMCwwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMyZGNcdWJiZmNcdWI0ZTRcdWM3NTggXHViZTVhXHVjNzQ0IFx1ZDU3NFx1YWNiMFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWFlMDhcdWM1NjFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI4NjEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJEVUdPVkkiLCJkZXNjcmlwdGlvbiI6IjxwPkluIGEgbGl0dGxlIHRvd24gY2FsbGVkIEtyaVx1MDE3ZSBsaXZlIE4gcGVvcGxlLiBFYWNoIG9mIHRoZW0gaGFzIGJvcnJvd2VkIHNvbWUgbW9uZXkgZnJvbSBleGFjdGx5IG9uZSBvdGhlciBpbmhhYml0YW50LiBOb3cgdGhlIHRpbWUgaGFzIGNvbWUgdG8gcGF5IGJhY2sgYWxsIHRoZSBkZWJ0cywgYnV0IHRoZSBwcm9ibGVtIGlzIHRoYXQgZXZlcnlib2R5IGhhcyBzcGVudCBhbGwgb2YgdGhlaXIgbW9uZXkhJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBtYWpvciBvZiBLcmlcdTAxN2UgaGFzIGRlY2lkZWQgdG8gc29sdmUgdGhpcyBwcm9ibGVtLiBUaGUgdG93biB3aWxsIGdpdmUgbW9uZXkgdG8gYSBmZXcgcGVvcGxlIHNvIHRoYXQgdGhleSBjYW4gcGF5IGJhY2sgdGhlaXIgZGVidHMuIFdoZW4gc29tZSBwZW9wbGUgZ2V0IHRoZWlyIG1vbmV5IGJhY2ssIGEgY2hhaW4gcmVhY3Rpb24gaXMgc3RhcnRlZCAtIGZvciBleGFtcGxlOiBwZXJzb24gQSBnZXRzIG1vbmV5IGZyb20gdGhlIGNpdHkuIFBlcnNvbiBBIHVzZXMgdGhhdCBtb25leSB0byBwYXkgdGhlIGRlYnQgdG93YXJkIHBlcnNvbiBCLiBQZXJzb24gQiB0aGVuIHVzZXMgdGhhdCBtb25leSB0byBwYXkgdGhlIGRlYnQgdG93YXJkcyBwZXJzb24gQyBldGMuIElmIHBlcnNvbiBCIGRpZG4mcnNxdW87dCBoYXZlIGVub3VnaCBtb25leSB0byBwYXkgYmFjayB0aGUgZGVidCwgdGhleSB3YWl0IHVudGlsIHRoZXkgZ2V0IGVub3VnaC4gSWYgdGhleSBoYXZlIG1vcmUgdGhhbiBlbm91Z2ggbW9uZXksIHBlcnNvbiBCIHdpbGwga2VlcCB3aGF0IGlzIGxlZnQgYWZ0ZXIgcGF5YmFjay4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QW5vdGhlciBleGFtcGxlOiBpZiB0d28gcGVvcGxlIGxpdmUgaW4gS3JpXHUwMTdlLCBhbmQgdGhleSBvd2UgJDEwMCB0byBlYWNoIG90aGVyLCB0aGUgdG93biB3aWxsIGdpdmUgJDEwMCB0byBvbmUgb2YgdGhlbSBzbyB0aGV5IGNhbiBwYXkgYmFjayB0aGUgZGVidCB0byB0aGUgb3RoZXIgb25lLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgdG8gY2FsY3VsYXRlIHRoZSBtaW5pbXVtIHRvdGFsIGFtb3VudCBvZiBtb25leSB0aGUgdG93biBoYXMgdG8gZ2l2ZSB0byBzb21lIHN1YnNldCBvZiB0aGUgaW5oYWJpdGFudHMgc28gdGhhdCBhZnRlciB0aGUgcGF5YmFjayBwcm90b2NvbCBkZXNjcmliZWQgYWJvdmUgYWxsIGRlYnRzIGFyZSBwYXllZC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgb25lIGludGVnZXIgTiAoMiAmbGU7IE4gJmxlOyAyMDAgMDAwKSwgbnVtYmVyIG9mIGluaGFiaXRhbnRzIG9mIEtyaVx1MDE3ZS4gVGhleSBhcmUgbnVtYmVyZWQgZnJvbSAxIHRvIE4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWluIHR3byBpbnRlZ2Vycywgc2VwYXJhdGVkIGJ5IHNwYWNlLiBJbiBpLXRoIG9mIHRob3NlIGxpbmVzLCBmaXJzdCBudW1iZXIgLSBBPHN1Yj5pPFwvc3ViPiByZXByZXNlbnRzIHRoZSBpZCBvZiB0aGUgcGVyc29uIGktdGggcGVyc29uIG93ZXMgbW9uZXkgdG8gKDEgJmxlOyBBPHN1Yj5pPFwvc3ViPiAmbGU7IE4sIEFpICZuZTsgaSksIGFuZCBzZWNvbmQgQjxzdWI+aTxcL3N1Yj4gcmVwcmVzZW50cyB0aGUgYW1tb3VudCBvZiB0aGUgZGVidCBpbiAkICgxICZsZTsgQjxzdWI+aTxcL3N1Yj4gJmxlOyAxMCAwMDApLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIG9uZSBpbnRlZ2VyIC0gdGhlIG1pbmltdW0gdG90YWwgYW1tb3VudCBvZiBtb25leSB0b3duIGhhcyB0byBnaXZlIHRvIGl0cyBpbmhhYml0YW50cyBzbyBhbGwgZGVidHMgYXJlIHJldHVybmVkLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==