وضعیت اقتصادی خراب شده است و به دلیل کمبود پول در گردش اعتبار بسیاری از کارخانجات مقروض شده‌اند و توانایی پرداخت بدهی خود را ندارند. حداکثر ۱۰۰ کارخانه موجود است.

کارخانه‌ها هم فروشنده و هم خریدارند؛ آن‌ها محصولات خود را می‌فروشند و مواد اولیه می‌خرند. بنابراین آن‌ها به هم قرض دارند. فردی ایده‌ی جدیدی به ذهنش رسید تا کارخانه‌ها قرض را با قرض پرداخت نمایند.

به عنوان مثال، فرض کنید کارخانه $A$، ۱۰۰ دلار به کارخانه‌ی $B$، ۵۰ دلار به کارخانه‌ی $C$ و کارخانه‌ی $C$، ۷۵ دلار به کارخانه‌ی $A$ مقروض است. مجموع این قرض‌ها ۲۲۵ دلار است. $A$ از اعتباری که نزد $C$ دارد استفاده می‌کند تا قسمتی از قرض خود را به $B$ بپردازد. با این کار قرض‌ها به صورت زیر در می‌آیند.

$$A \quad to \quad B \quad $25$$ $$B \quad to \quad C \quad $50$$

$$C \quad to \quad B \quad $75$$ با تکرار این عمل می‌توان مجموع قرض‌ها را به حداقل رساند؛ لیست قرض‌ها به صورت زیر در می‌آید. $$A \quad to \quad B \quad $25$$

$$C \quad to \quad B \quad $25$$

برنامه‌ای بنویسید تا بدهی کارخانه‌ها را به این صورت پرداخت نماید.

1. لیست قرض‌ها را از فایل ورودی بخوانید و این ارقام را در فایل خروجی کارخانه و مقدار قرضی که کارخانه‌ی اول به دومی دارد. ورودی شامل لیست‌های مختلفی است که با یک سطر خالی از هم جدا شده‌اند، چنان که در مثال مشاهده می‌شود.
2. لیست قرض‌ها را مجددا بازسازی کنید تا مجموع قرض کارخانه‌ها کمینه شود. لیست جدید را به همان قالب فایل ورودی در فایل خروجی بنویسید.
3. مجموع کل قرض‌ها را در انتهای فایل خروجی بنویسید.

به مثال زیر توجه کنید.

• سوال بعد