Şarlar#1381
Bildiyiniz kimi, bu müsabiqədə komandalar problemləri həll etdikcə onlara şarlar verilir. Lakin, keçmişdə bu, bəzən çətin logistik problemlərə səbəb olub.
Bir müsabiqə məkanı iki otaqdan ibarət idi: A və B, hər birində şar ehtiyatı var idi. Müsabiqədə N komanda iştirak edirdi və hər komanda fərqli yerlərdə oturmuşdu; bəziləri otaq A-ya, digərləri isə otaq B-yə daha yaxın idi. Hər bir komandanın ehtiyac duyduğu şarların sayı, otaq A və otaq B-yə olan məsafələri verilib. Əgər şarlar optimal şəkildə otaq A və otaq B-dən paylansa, bütün şarların öz komandalarına çatdırılması üçün lazım olan ən az ümumi məsafə nə qədər olar? Bu məsələdə, müsabiqə təşkilatçılarının ucuz davrandığını və yalnız bir rəngdə şar aldığını fərz edin.
Məlumat faylında bir neçə test var. Hər test bir sətrdə üç tam ədəd ilə başlayır:
N A B
burada N komandaların sayı (1 \le N \le 1000), A və B isə müvafiq olaraq otaq A və otaq B-dəki şarların sayıdır (1 \le A, B \le 10000).
Növbəti N sətrin hər birində bir komanda üçün üç tam ədəd verilir:
K D_A D_B
burada K həmin komandanın ehtiyacı olan şarların ümumi sayı, D_A otaq A-ya, D_B isə otaq B-yə olan məsafədir (1 \le D_A, D_B \le 1000). Qəbul edə bilərsiniz ki, şarlar kifayət qədərdir: \sum_i K_i \le A + B. Məlumat faylının sonu üç 0 olan sətrlə bitir.
Hər test üçün bütün şarların çatdırılması üçün tələb olunan minimum ümumi məsafəni təmsil edən bir tam ədəd çap edin. Yalnız gediş məsafəsi hesablanır, şarı aparan otaqdan komandaya qədər. Geri qayıdışı otaq A və ya otaq B-yə hesablamayın. Hər cavabı ayrıca sətrdə və boşluqsuz çap edin. Cavablar arasında boş sətr buraxmayın.
Nümunə 1