Представьте себе, что в вашей дружеской компании три человека: A, B и С. При этом A должен B 20 рублей, а B должен C 20 рублей. Общая сумма задолженностей равна 40 рублей. Можно заметить, что задолженности в этом случае устроены не самым оптимальным образом. Перераспределим задолженности следующим образом: пусть A должен C 20 рублей, а B ничего никому не должен. Смысл задолженностей не изменился, а сумма всех задолженностей стала равна 20 рублей.
Эта задача обобщает описанный пример. Представьте, что в вашей дружеской компании n человек, и известны задолженности между людьми. Оптимизируйте заданные задолженности, не меняя их смысла. Другими словами в итоге для каждого человека разность того, сколько он должен отдать, и сколько он должен получить, должна сохраниться. Выведите минимальную сумму всех задолженностей в оптимальном распределении задолженностей. Посмотрите пояснение тестовых примеров для лучшего понимания задачи.
Выходные данные
Выведите единственное целое число — минимальную сумму задолженностей в оптимальном распределении.
Примечание
В первом примере можно считать, что человек с номером 1 должен человеку с номером 2 8 рублей, человеку с номером 3 1 рубль и человеку с номером 4 1 рубль. Больше никто никому не должен. В итоге суммарная задолженность равна 10.
Во втором примере нет никаких задолженностей.
В третьем примере можно аннулировать все задолженности.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
1 2 10
2 3 1
2 4 1
|
10
|
|
2
|
3 0
|
0
|
|
3
|
4 3
1 2 1
2 3 1
3 1 1
|
0
|