Розрахунок боргів за шматками піци

Піца-криза в лігві! Порожні коробки з-під піци скрізь. Чотири черепашки, нуль шматків залишилось. Майстер Сплінтер дивиться на своїх учнів і каже: "Мабуть, настав час навчитися мудріше ділитися піцою, сини мої!"

Ок, ось у чому справа. Леонардо, Мікеланджело, Донателло та Рафаель весь тиждень обмінювалися шматками піци один з одним, і теперніхто не пам'ятає, хто кому скільки винен. Усі винні один одному, але в жодної черепашки немає достатньо шматків під рукою, щоб розплатитися з усіма, хоча математично цифри мають сходитися.

Дозвольте показати ситуацію з піца-боргами на малюнку (а). Граф показує, скільки шматків винні одна одній чотири черепашки (Лео, Майкі, Донні та Раф). Наприклад, Лео винен Майкі 50 шматків, а Майкі винен Лео 150 шматків. (Ага, таке буває - дві черепашки можуть бути винними одна одній одночасно!) Щоб усе врегулювати, їм знадобилося б передати туди-сюди 380 шматків піци.

Але зачекайте! Вивчивши цей безлад, я зрозумів, що є розумніший спосіб. Ми марнуємо піцу на непотрібні передачі! Глядіть:

1. Донні винен Рафу рівно 30 шматків, а Раф винен Лео ті самі 30 шматків. То навіщо посередник? Донні може заплатити безпосередньо Лео, і ми виключаємо Рафа з ланцюжка!

2. Але стривайте - Лео вже винен Донні 100 шматків. Тож насправді Лео потрібно заплатити Донні лише різницю: 70 шматків.

3. Та сама ідея з Майкі і Лео. Майкі винен Лео 150 шматків, але Лео винен Майкі 50 шматків. Чистий результат? Майкі платить Лео лише 100 шматків. Тепер у нас малюнок (б), і потрібно всього 190 шматків. Це 200 шматків економії, або 53%!

4. Але можна ще краще! Замість того, щоб Майкі давав 100 шматків Лео, а потім Лео розвертається і дає 70 шматків Донні, чому б Майкі не віддати 70 шматків безпосередньо Донні? Тоді Майкі дає лише 30 шматків Лео. Дивіться на малюнок (в) - нам потрібно всього 120 шматків! Це зменшення на 260 шматків, або 68%! Ковабунга!

У мене є всі дані про те, хто кому винен, але я не можу знайти оптимальний спосіб мінімізувати потрібну піцу. Чи можете ви написати програму, яка знайде мінімальну кількість шматків, потрібну для погашення всіх боргів?