• محدودیت زمان: ۰.۵ ثانیه
• محدودیت حافظه: ۱۲۸ مگابایت

برای کنترل جهان باید از کنترل کولر شروع کرد!

"رادزینکا دوبرامیل ویچشسلافوویچ"

قرار شده‌است که در عمارت، انتخاباتی برگزار شود تا شخص منتخب خانه را اداره کند. آقای خطری، یکی از اعضای خانه است که میخواهد برای این کار نامزد بشود. او مردی به شدت منطقی بوده و معتقد است که کولر باید خاموش باشد! انگیزه‌ی شرکت او در انتخابات هم همین است...

هنگام ثبت‌نام نامزد از او خواسته شد تا نام انتخاباتی خود را وارد کند. او که احساس می‌کرد که اسم «خطری» رای‌دهندگان را خواهد ترساند تصمیم گرفت که نام دیگری را وارد کند. او دستش را برروی صفحه کلید گذاشت (تکنولوژی در عمارت بالاست) و تعدادی کلید را فشار داد تا اسم انتخاباتی‌اش را وارد کند. می‌دانیم که صفحه کلید تنها شامل حروف و دکمه‌ی CapsLock می‌باشد و ابتدا CapsLock خاموش بوده است. با گرفتن دکمه‌هایی که آقای خطری زده است بگویید که نام انتخاباتی او چیست.

اگر CapsLock روشن باشد، حروف بزرگ نوشته خواهند شد و اگر خاموش باشد حروف کوچک نوشته خواهند شد. همچنین با زدن دکمه‌ی CapsLock، وضعیت CapsLock برعکس خواهد شد.

ورودی🔗

در سطر اول ورودی عدد $n$ آمده‌ است که نمایانگر تعداد دکمه‌هایی است که آقای خطری وارد کرده است.

سپس در $n$ سطر بعدی، در هر سطر، دکمه‌ای که آقای خطری زده است آمده است. این دکمه یا یکی از حروف کوچک انگلیسی است و یا دکمه‌ی CapsLock که دکمه‌ی CapsLock در ورودی به صورت "CAPS" آمده است.

تضمین می‌شود که حداقل یک دکمه از حروف زده شده است.

$3 \le n \le 100$

خروجی🔗

در تنها سطر خروجی نام انتخاباتی آقای خطری را خروجی دهید.

مثال🔗

ورودی نمونه ۱🔗

10
d
CAPS
a
n
g
CAPS
e
r
CAPS
y

خروجی نمونه ۱🔗

dANGerY

ورودی نمونه ۲🔗

3
z
j
u

خروجی نمونه ۲🔗

zju

• محدودیت زمان: ۰.۵ ثانیه
• محدودیت حافظه: ۱۲۸ مگابایت

برای کنترل جهان باید از کنترل کولر شروع کرد!

«رادزینکا دوبرامیل ویچشسلافوویچ»

به تازگی مطّلع شدیم که علاوه بر آقای خطری، آقای بی‌خطر هم می‌خواهد برای شرکت در «انتخابات ریاست کولر» نامزد شود. آقای خطری پس از اطّلاع از این خبر، بسیار نگران می‌شود و تصمیم می‌گیرد با آقای بی‌خطر مذاکره کند و او را از این امر منصرف کند.

امّا آقای بی‌خطر که از آقای خطری بسیار می‌ترسد، شروع به فرار می‌کند تا این که در ترامپولین شماره $n$ از مسیر ترامپولینی گیر می‌افتد.

مسیر ترامپولینی متشکل از $n$ ترامپولین است که در یک صف دور کره‌ی زمین قرار دارند و به ترتیب ساعت‌گرد از $1$ تا $n$ شماره‌گذاری شده اند. اگر کسی روی ترامپولین شماره $i$ بپرد، $i$ ترامپولین (بطور ساعت‌گرد) جلوتر خواهد رفت. این روند تا زمانی که دو نفر در یک خانه قرار نگیرند ادامه خواهد داشت!

مثلن اگر $n=3$ و کسی روی ترامپولین اوّل بپرد، ابتدا یک واحد جلو می‌رود و به ترامپولین دوم می‌رسد. سپس دو واحد جلو خواهد رفت و به ترامپولین اوّل بازخواهد گشت. این روند مدام تکرار می‌شود.

آقای خطری که به دنبال آقای بی‌خطر است، به مسیر ترامپولینی می‌رسد امّا از شماره‌ی ترامپولین‌ها آگاه نیست. حال او از شما می‌خواهد به او بگویید به ازای چند انتخاب ترامپولین اوّلیّه، او سرانجام آقای بی‌خطر را خواهد یافت.

ورودی🔗

در ورودی تنها یک عدد طبیعی $n$ داده شده است.

$1 \le n \le 10^9$

خروجی🔗

در تنها خط خروجی باید یک عدد صحیح چاپ کنید که برابر تعداد ترامپ‌لین‌هایی است که آقای خطری با شروع از آن‌ها سرانجام به ترامپ‌لین آقای بی‌خطر می‌رسد.

مثال🔗

ورودی نمونه ۱🔗

1

خروجی نمونه ۱🔗

1

در این نمونه، آقای خطری با شروع از ترامپ‌لین شماره ۱ همیشه در آن می‌ماند.

ورودی نمونه ۲🔗

6

خروجی نمونه ۲🔗

2

در این نمونه، آقای خطری می‌تواند از ترامپ‌لین شماره ۳ و یا ۶ شروع کند. در صورت شروع از ترامپ‌لین شماره ۳، پس از یک حرکت به ترامپ‌لین شماره ۶ می‌رسد.

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

برای کنترل جهان باید از کنترل کولر شروع کرد.

«رادزینکا دوبرامیل ویچشسلافوویچ»

متاسّفانه یا خوش‌بختانه آقای خطری نتوانست ترامپولین درستی را انتخاب کند و تلاش‌های شبانه‌روزی‌ش برای مذاکره با آقای بی‌خطر به شکست منتهی شد. پس منشی او تصمیم گرفت مستقیماً با طرفداران آقای بی‌خطر صحبت کند. شایان ذکر است آخرین اخبارِ موجود حاکی از آن است که دو نامزد شهیر انتخابات، همچنان در حال پرش بر روی ترامپولین‌ها هستند و تلاش‌ها در پی نجاتشان هنوز ادامه دارد.

در عمارت هر فرد رای دهنده یک درجه‌ی اجتماعی دارد و تعداد افرادی که درجه‌ی اجتماعی‌شان $i$ است، دقیقن $i$ نفر است. ($1 \leq i \leq n$) نحوه‌ی رای دادن افراد هر درجه، از روی رای افراد درجه‌ی بعدی آن‌ها مشخّص می‌شود؛ به استثنای افراد درجه $n$ که مقام بسیار والایی دارند و خودشان مشخّص می‌کنند که به چه کسی رای بدهند.

مثلاً در صورتی که $n = 4$ رای فرد درجه ۱ از روی افراد درجه ۲ مشخّص می‌شود، که رای خود آن‌ها از روی افراد درجه ۳ مشخّص می‌شود. رای افراد درجه ۳ نیز از روی افراد درجه ۴ مشخّص می‌شود. امّا افراد درجه‌ ۴ رایشان مستقل از رای بقیّه مشخّص خواهد شد.

فرد $i$اُم از درجه‌ی $j$اُم($1 \leq i \leq j < n$) تنها در صورتی به آقای خطری رای می‌دهد که حداقل یکی از افراد $i$اُم و $i+1$ام از درجه‌ی $j + 1$اُم قصد داشته باشند به آقای خطری رای دهند.

در این میان منشی آقای خطری می‌‌تواند با حداکثر $k$ تا از افراد صحبت کند و رای آن‌ها را عوض کند. اگر رای کسی عوض شود، رای تمام افرادی که رایشان بستگی به رای او داشت نیز طبق تعریف پاراگراف قبل به روز رسانی خواهد شد.

به شما $n$ و $k$ و آرای اوّلیّه‌ی افراد با درجه‌ی اجتماعی $n$ داده می‌شود و باید بگویید اگر منشی آقای خطری به صورت بهینه افرادی را برای صحبت کردن انتخاب کند، چند نفر به آقای خطری رای خواهند داد.

ورودی🔗

در اوّلین خط ورودی به ترتیب دو عدد صحیح $n$ و $k$ آمده است که با یک کاراکتر space از هم جدا شده‌اند.

در خط دوم رشته‌ای به طول $n$ خواهد آمد؛ حرف $i$اُم آن در صورتی که برابر 'K' باشد یعنی فرد $i$اُم از درجه‌ی $n$ به طور پیش‌فرض به آقای خطری رای می‌دهد و در صورتی که برابر 'B' باشد یعنی آن فرد به طور پیش‌فرض به آقای بی خطر رای می‌دهد.

$1 \le n \le 500$ $0 \le k \le 500$

خروجی🔗

در تنها خط خروجی جواب مطلوب مساله را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

3 0
BKK

خروجی نمونه ۱🔗

5

ورودی نمونه ۲🔗

3 1
BKK

خروجی نمونه ۲🔗

6

ورودی نمونه ۳🔗

6 1
BBBBBB

خروجی نمونه ۳🔗

12

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

برای کنترل جهان باید از کنترل کولر شروع کرد.

«رادزینکا دوبرامیل ویچشسلافوویچ»

با کمک شما در سوال قبل، آقای خطری موفق شد که با اکثریت آرا انتخابات را ببرد و به عنوان مدیر عمارت انتخاب شود. در اولین روز پس از انتخاب، در اولین تصمیم، او کولر خانه را برای همیشه خاموش کرد. سپس به پیدا کردن مشکلات عمارت مشغول شد. در پرس‌و‌جوهای اولیه‌ای که انجام داد به این نتیجه رسید که یکی از بزرگترین مشکلات خانه، سوسک بزرگی است که سال‌هاست در آن خانه زندگی می‌کند و قصد رفتن از آنجا را ندارد؛ از این رو آقای خطری تصمیم گرفت که برای همیشه از شر این سوسک راحت شود. او برای کشتن این سوسک عجیب دمپایی خاصی از شهر خریده است تا با آن، این سوسک را بکشد. کشتن این سوسک به این راحتی‌ها هم نیست چرا که این با کشتن این سوسک، امکان دارد سوسک‌های جدیدی با نژادهای دیگری از دل این سوسک به وجود بیایند. در مجموع می‌توان گفت که $n$ نژاد سوسک وجود دارد که سوسک بزرگ عمارت از نوع اول می‌باشد.

هر نژاد از سوسک (مانند $i$)، چند ویژگی به صورت زیر دارد:

اول $a_i$، که اگر به او این تعداد ضربه با دمپایی بزنیم، می‌میرد بدون اینکه سوسک جدیدی از او به وجود بیاید.

دوم $b_i$، که اگر به او به این تعداد ضربه با دمپایی بزنیم، می‌میرد اما سوسک‌های جدیدی به وجود می‌آیند.

سوم لیستی از سوسک ها که در صورت مرگ سوسک با $b_i$ ضربه دمپایی، از او به وجود می‌آیند.

آقای خطری می‌خواهد از شر سوسک‌ها راحت شود اما با توجه به زمان محدودی که او دارد و باید به دیگر مشکلات خانه برسد، می‌خواهد کمترین تعداد ضربه دمپایی را بزند تا از شر تمامی سوسک‌ها راحت شود. به او بگویید که این کمترین تعداد چقدر است تا او بتواند برنامه ریزی کند.

ورودی🔗

در اولین سطر ورودی عدد $n$ می‌آید که نمایانگر تعداد نژاد سوسک‌ها می‌باشد.

سپس در هر یک از $n$ سطر بعدی، در سطر $i$، توضیحات مربوط به نژاد $i$ سوسک‌ها به این صورت می‌آید:

ابتدا عدد $b_i$ می‌آید. سپس عدد $a_i$ خواهد آمد که توضیح این دو ورودی بالاتر گفته شده است.

سپس یک عدد $r_i$ می‌آید که نمایانگر تعداد سوسک‌هایی است که از مرگ این سوسک با $b_i$ ضربه به وجود می‌آید. بعد از آن $r_i$ عدد متمایز بین ۱ و $n$ می‌آید که هر کدام نمایانگر این است که در صورت مرگ این سوسک با $b_i$ ضربه، یک سوسک با این نژاد به وجود می‌آید.

$1 \le n \le 200\ 000$ $1 \le a_i, b_i \le 10^9$

مجموع $r_i$ ها حداکثر برابر $1\ 000\ 000$ است.

خروجی🔗

در تنها سطر خروجی کمترین تعداد ضربه دمپایی که لازم است تا تمام سوسک‌ها از بین بروند را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

3
1 3 2 1 2
1 1 1 1
1 1 1 2

خروجی نمونه ۱🔗

3

ورودی نمونه ۲🔗

3
2 7 1 2
2 4 1 3
2 1 1 1

خروجی نمونه ۲🔗

5

در این نمونه ابتدا سوسک اول را با دو ضربه میکشیم. سپس سوسک از نژاد دوم را با دو ضربه میکشیم و در نهایت سوسک از نژاد سوم که از مرگ سوسک با نژاد دوم به وجود آمده است را با یک ضربه میکشم و هیچ سوسک جدیدی هم از مرگ این سوسک به وجود نمی‌آید.

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

برای کنترل جهان باید از کنترل کولر شروع کرد.

«رادزینکا دوبرامیل ویچشسلافوویچ»

اگرچه آقای خطری بسیار انسان جدی‌ای می‌باشد اما علاقه‌ی او به شیرجه در استخر غیرقابل وصف است! هر چه هم که عمق استخر بیشتر باشد، لذت شیرجه در آن هم بیشتر می‌شود؛ از این رو آقای خطری تصمیم گرفت که سری به استخر‌های عمارت بزند. برای این کار او پیش آقای برداری رفته است تا از او کمک بخواهد. آقای برداری مسئول برداشتن افراد و جابجایی ایشان است؛ از این رو او باید برنامه‌ی گردش آقای خطری را بریزد و او را بین استخر‌های مختلف جابجا کند.

نقشه‌ی عمارت به صورت یک جدول $n \times m$ می‌باشد که در بعضی از خانه‌های این جدول استخر نیز وجود دارد. در این عمارت از یک خانه می‌توان به یکی از خانه‌های چپ، بالا، راست و یا پایین آن خانه (در صورت وجود) رفت و این کار به اندازه‌ی یک شتیل برای آقای خطری خرج دارد؛ یعنی او باید به آقای برداری برای این جابجایی یک شتیل بدهد. همچنین مسئول هر استخر در صورتی که آقای برداری آقای خطری را به آن استخر بیاورد حاضر است مقداری شتیل به آقای برداری بدهد.

آقای خطری انسان جدی‌ای است و قوانین خاص خودش را دارد؛ از این رو او به آقای برداری دستور داده است که برنامه‌ را جوری بریزد که عمق استخر‌هایی که مشاهده می‌شوند یک روند اکیدا صعودی داشته باشد؛ یعنی اگر دنباله‌ی عمق استخر‌هایی را که آقای خطری از آن‌ها دیدن کرده است به ترتیب زمانی بنویسیم، این دنباله اکیدا صعودی بشود.

حال با تمام این سه پاراگراف توضیحی که داده شد، بگویید که بیشترین مقدار شتیلی که آقای برداری می‌تواند به دست آورد چقدر می‌باشد. دقت کنید که آقای برداری هزینه‌ی دیدن اولین استخر را به صورت اشانتیون می‌بخشد یعنی برای دیدن اولین استخر نیازی به دادن هزینه‌ی جابجایی به آقای برداری نمی‌باشد.

ورودی🔗

در سطر اول ورودی دو عدد $n$ و $m$ آمده است که نمایانگر ابعاد عمارت می‌باشند.

سپس در $n$ سطر، در هر سطر $m$ عدد می‌آید که عدد $j$ در سطر $i$، $h_{i,j}$ بوده و نمایانگر عمق استخر موجود در خانه‌ی $(i, j)$ جدول می‌باشد. دقت کنید که اگر عمق استخری ۰ باشد، به این معنی است که دیگر آنجا استخری نیست و درنتیجه آنجا استخری وجود ندارد که بتوان از آن دیدن کرد.

بعد از آن در $n$ سطر، در هر سطر $m$ عدد می‌آید که عدد $j$ در سطر $i$، $c_{i,j}$ بوده و نمایانگر مقدار شتیلی است که مسئول آن استخر (در صورت آوردن آقای خطری) به آقای برداری می‌دهد.

$1 \le n, m \le 1\ 000$ $0 \le h_{i, j} \le 1\ 000\ 000$ $0 \le c_{i, j} \le 1\ 000\ 000$

خروجی🔗

در تنها سطر خروجی بیشینه مقدار شتیلی که آقای برداری می‌تواند به دست بیاورد را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

2 2
1 2
3 4
2 2
2 2

خروجی نمونه ۱🔗

12

ورودی نمونه ۲🔗

3 3
1 2 3
3 2 1
2 3 1
1 4 5
5 4 1
4 5 1

خروجی نمونه ۲🔗

17

در این نمونه ابتدا به استخر در خانه‌ی (2,3) رفته، سپس به ترتیب به سراغ استخر‌های خانه‌های (3,1) و (1,3) میرویم. هزینه‌ی جابجایی ۷ و پولی که مسئولین استخر می‌دهند ۱۰ خواهد بود که در مجموع ۱۷ می‌شود.

• محدودیت زمان: ۳ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

برای کنترل جهان باید از کنترل کولر شروع کرد.

«رادزینکا دوبرامیل ویچشسلافوویچ»

متاسفانه در عمارت دو دوقطبی ایجاد شده است!!! اولی را یک بچه با یک سری آهن و آهن‌ربا به وجود آورده است و دومی هم تعدادی از اعضای عمارت هستند که در بین آنها عده‌ای معتقد هستند که امروز غذا باید خورشت قرمه‌سبزی باشد درحالیکه عد‌‌ه‌ی دیگر از خورشت قیمه خوششان می‌آید. متاسفانه کار دارد به جاهای باریک می‌کشد و آقای خطری باید هر چه زودتر به این معضل پایان دهد.

او برای حل این مشکل تصمیم گرفت که تعدادی از افراد عمارت را انتخاب کند تا مشکل را حل کنند. در این عمارت هر شخصی یک توانایی ذهنی دارد و آقای خطری باید جوری افراد را انتخاب کند که مجموع توانایی افراد بیشینه باشد. همچنین نکته‌ی مهم دیگری که وجود دارد این است که هر دونفری از این افراد باید بتوانند با هم بسازند. می‌دانیم که هر فرد با تمام افرادی که غذای مورد علاقه‌‌شان با او یکسان است می‌سازد و همچنین تعدادی از افراد از یک طرف می‌توانند با تعدادی از افراد از طرف مقابل نیز بسازند.

حال با گرفتن روابط بین افراد بگویید که بیشینه مجموع توانایی افرادی که آقای خطری می‌تواند انتخاب کند به طوری که هر دو نفری از آنها با هم بسازند چقدر است.

ورودی🔗

در سطر اول ورودی دو عدد $n$ و $m$ و $k$ آمده است که به ترتیب نمایانگر افرادی است که قرمه‌سبزی و قیمه دوست دارند و تعداد روابط سازندگی بین این دو گروه است.

سپس در $k$ سطر بعدی، در هر سطر، یک دو عدد $a$ و $b$ آمده است که نمایانگر این است که فرد شماره‌ی $a$ از افرادی که قرمه‌سبزی دوست دارند می‌تواند با فرد شماره‌ی $b$ از افرادی که قیمه دوست دارند بسازد. دقت کنید که تمام افرادی که قرمه دوست دارند باهم می‌سازند. همینگونه است برای تمام افرادی که قرمه‌سبزی دوست دارند.

سپس در خط بعدی $n$ عدد آمده است که عدد $i$، نمایانگر توانایی ذهنی شخص شماره‌ی $i$ از افرادی که قرمه‌سبزی دوست دارند، میباشد. این اعداد طبیعی حداکثر برابر یک میلیارد می‌باشند.

و در نهایت در خط بعدی $m$ عدد آمده است که عدد $i$، نمایانگر توانایی ذهنی شخص شماره‌ی $i$ از افرادی که قیمه دوست دارند، میباشد.

$1 \le n, m \le 400$ $0 \le k \le n \times m$

خروجی🔗

در تنها سطر خروجی بیشینه مجموع توانایی ذهنی افراد انتخابی را خروجی دهید.

مثال🔗

ورودی نمونه ۱🔗

2 2 3
1 2
1 1
2 1
1 5
2 2

خروجی نمونه ۱🔗

8

ورودی نمونه ۲🔗

2 3 1
1 1
1 1
5 5 5

خروجی نمونه ۲🔗

15

در این نمونه بهتر است که فقط سه نفری که قیمه دوست دارند را انتخاب کنیم.