Şarlar
Müsabiqə zamanı bildiyiniz kimi, komandalar problemləri həll etdikcə onlara şarlar verilir. Lakin keçmişdə bu, bəzən çətin logistik problemlər yaratmışdır.
Bir müsabiqə keçirilən məkan iki otaq saxlayırdı: A və B, hər biri şar ehtiyatı ilə dolu idi. Müsabiqədə iştirak edən N komanda var idi, hər biri müxtəlif 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ı və hər bir komandanın otaq A və otaq B-dən olan məsafəsi verildikdə, şarların müvafiq komandalarına çatdırılması zamanı bütün şarların keçməli olduğu minimum ümumi məsafə nə qədərdir, əgər onlar otaq A və otaq B-dən optimal şəkildə paylanarsa? Bu problemin məqsədləri üçün, müsabiqə heyətinin ucuz olduğunu və yalnız bir rəngli şar aldığını fərz edin.
Giriş verilənləri
Məlumat faylında bir neçə test halı olacaq. Hər bir test halı üç tam ədəddən ibarət bir sətirlə başlayacaq:
N A B
burada N komandaların sayıdır (1 ≤ N ≤ 1000), və A və B otaq A və otaq B-dəki şarların sayıdır (1 ≤ A, B ≤ 10000).
Növbəti N sətirdə hər bir komanda üçün üç tam ədəd olacaq:
K D_A D_B
burada K bu komandanın ehtiyac duyacağı ümumi şarların sayıdır, D_A bu komandanın otaq A-dan olan məsafəsidir, və D_B bu komandanın otaq B-dən olan məsafəsidir (1 ≤ D_A, D_B ≤ 1000). Şarların kifayət qədər olduğunu fərz edə bilərsiniz - yəni, ∑_i K_i ≤ A + B. Məlumat faylı üç 0 olan bir sətirlə bitəcək.
Çıxış verilənləri
Hər bir test halı üçün, bütün şarların çatdırılması üçün keçməli olan minimum ümumi məsafəni təmsil edən bir tam ədəd çıxarın. Yalnız gedən yolu sayın, A və ya B-dən komandaya. Qaçanın otaq A və ya otaq B-yə qayıtmalı olduğu məsafəni saymayın. Hər bir tam ədədi öz sətirində boşluqsuz çap edin. Cavablar arasında boş sətir çap etməyin.