Mobil#2682

Mobil

1 saniyə

64 meqabayt

Çox asan

Siz yəqin ki, muzeylərin və ya hava limanlarının tavanlarından asılmış mobil kompozisiyaları (mobilləri) görmüsünüz. Bu məsələdə biz, tək bir tellə tavana asılmış və fırlanma nöqtəsinə birləşdirilmiş bir qolun üzərində dayanan mobile baxacağıq (qolun özü də tel kimidir). Qolun hər iki ucunda ya başqa bir qol asılıb, ya da bir ağırlıq yerləşdirilib (adətən hansısa struktur şəklində). Məşhur mobil sənətçisi Aleksandr Kolderin hazırladığı bir nümunəyə aşağıda baxa bilərsiniz.

Bəzi mobillər sadə, bəziləri isə olduqca mürəkkəb olur. Estetik dəyərlərindən əlavə, onlar tarazlıqda olmalıdır. Xatırlayın ki, əgər fırlanma nöqtəsindən sola olan məsafə $d_{L}$ d_L, sağa olan məsafə isə $d_{R}$ d_R-dirsə, qol tarazlıqda olacaq, əgər sol ucda olan ağırlıqla $d_{L}$ d_L-ın hasili sağ ucda olan ağırlıqla $d_{R}$ d_R-ın hasilinə bərabər olarsa. (Qolun və tellərin ağırlığı nəzərə alınmır.)

Məsələn, aşağıda təsvir olunan mobili nəzərdən keçirin. Əgər $1$ -ci ağırlıq $8$ vahiddirsə, o zaman $2$ , $3$ , $4$ və $5$ nömrəli ağırlıqlar müvafiq olaraq $2$ , $6$ , $4$ və $4$ vahid olmalıdır. Əgər mobilin strukturunu (yəni, qolların düzülüşünü və fırlanma nöqtələrinin yerləşməsini) və bir ağırlığın dəyərini bilirsinizsə, bütün ağırlıqları hesablamaq olar. Sizin buradakı vəzifəniz də məhz budur—demək olar ki. Çətinlik ondadır ki, bütün ağırlıqlar tam ədədlər olmalıdır. Sizə bir ağırlığın minimal qiyməti verilir və digər ağırlıqları da elə seçməlisiniz ki, hamısı tam ədəd olsun. Bu səbəbdən də, bəzən bu verilmiş minimal ağırlığı bir qədər artırmaq lazım gəlir.

Giriş

Hər test üçün giriş aşağıdakı kimi başlayır: birinci sətirdə $n$ — mobilin qollarının sayı olan müsbət tam ədəd verilir. Qollar $1$ -dən $n$ -ə kimi nömrələnmişdir. Sonrakı $n$ sətir müvafiq ardıcıllıqla qolları təsvir edir və aşağıdakı formadadır:

$d_{L} d_{R} type_{L} type_{R} n_{L} n_{R}$ d_L\\ d_R\\ \text{type}_L\\ \text{type}_R\\ n_L\\ n_R

Burada $d_{L}$ d_L və $d_{R}$ d_R — fırlanma nöqtəsindən qolun sol və sağ uclarına olan məsafələri göstərən, $20$ -dən çox olmayan tam ədədlərdir; $type_{L}$ \text{type}_L və $type_{R}$ \text{type}_R — uyğun olaraq, solda və sağda ya bir ağırlıq ( $W$ ), ya da bir qol ( $A$ ) asıldığını göstərən simvollardır; $n_{L}$ n_L və $n_{R}$ n_R — müvafiq olaraq solda və sağda yerləşən ağırlığın və ya qolun nömrəsidir. Ağırlıqların nömrələnməsi $1$ -dən başlayır və ardıcıldır. Heç bir qol tavandan $6$ qoldan çox uzaqda yerləşmir. Yuxarıdakı nümunədə ən altda yerləşən qol tavandan $3$ qol uzaqlığındadır.

Qolların təsvirindən sonra belə bir sətir gəlir: $m w$ , burada $m$ nömrəli ağırlığın ən azı $w$ olmasını tələb edir, $1 l e q w l e q 20$ 1 \\leq w \\leq 20.

Sonuncu testdən sonra bir sətirdə $0$ verilir.

Çıxış

Hər test üçün belə bir sətir çıxış edin: $m$ nömrəli ağırlıq ən azı $w$ olduqda, mobilin mümkün olan ən azı ümumi ağırlığını verin. Nümunə çıxışdakı formata əməl edin. Bütün çıxış nəticələrinin $1 0^{9}$ 10^9-dan kiçik olacağına əmin ola bilərsiniz.

Nümunələr

Nümunə 1