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

باتری تلفن همراه مرد مالیاتچی‌ تمام شده‌است.

می‌دانیم تلفن مرد مالیاتچی برای اینکه از $i$ درصد شارژ به $i + 1$ درصد برسد $i + 1$ دقیقه زمان می‌برد.

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

ورودی🔗

در یک خط عدد $k$ به شما داده می‌شود.

$1 \le k \le 100$

خروجی🔗

در یک خط مجموع دقایقی که طول می‌کشد را چاپ کنید.

مثال🔗

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

1

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

1

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

3

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

6

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

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

ورودی🔗

در یک خط و شامل سه عدد طبیعی $a$ و $b$ و $c$ است که نمره کسب شده یک دانشجو در بخش‌های مختلف است. $1 \leq a, b, c \leq 100$

خروجی🔗

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

مثال🔗

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

9 1 1

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

4

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

100 100 99

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

100

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

در شهر مرد مالیاتچی مردم به زبان Taxlang با یک دیگر سخن میگویند که شامل حروف T و A و X و M و N میباشد. بدلیل اینکه این شهر مربوط به سال 1717 قبل از میلاد است برای نوشتن یک عبارت، بلوک هایی متناظر با کاراکتر های آنرا بر روی دیواره ی غارها حک میکنند. به طور دقیق تر این زبان از چپ به راست خوانده شده و شامل بلوک هایی به طول ۵ و ارتفاع ۳ میباشد و هر بلوک دقیقا با یکی از حروف این زبان متناظر است که با مشاهده ورودی های نمونه میتوانید به راحتی تناظر میان آنها را کشف کنید.

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

ورودی🔗

ورودی شامل سه خط از کاراکترها می‌باشد. طول هر خط مضربی از ۵ بوده و حداکثر ۱۰۰ می‌باشد.

تضمین می‌شود که ورودی معتبر بوده و دقیقا یک ترجمه مناسب برای آن وجود دارد.

خروجی🔗

در تنها سطر خروجی ترجمه متن داده شده را خروجی دهید.

مثال🔗

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

*****
oo*oo
oo*oo

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

T

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

oo*oo
o***o
*ooo*

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

A

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

*ooo*
oo*oo
*ooo*

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

X

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

**o**
*o*o*
*ooo*

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

M

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

*ooo*
*o*o*
*ooo*

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

N

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

*****oo*oo*ooo***o**oo*oo*ooo*
oo*ooo***ooo*oo*o*o*o***o*o*o*
oo*oo*ooo**ooo**ooo**ooo**ooo*

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

TAXMAN

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

در اداره مالیات $n$ مالیات‌چی وجود دارد.

مالیات‌چی $i$ ام می‌تواند از $a_i$ نفر خاص در شهر مالیات بگیرد.

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

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

مثلا مالیات چی اول و دوم هر کدام می‌توانند به ترتیب از ۷ و ۸ نفر در شهر مالیات بگیرند اما ۳ نفر از این افراد مشترک است، پس چنانچه بخواهیم دو نفر مالیات‌چی نگه داریم و این دو نفر را انتخاب کنیم ما از ۱۲ نفر می‌توانیم مالیات بگیریم نه از ۱۵ نفر.

برای فهم بهتر سوال بخش ورودی را بخوانید.

ورودی🔗

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

سپس در خط بعد $n$ عدد که $a_i$ هاست به شما داده می‌شود.

در خط سوم $q$ به شما داده می‌شود و در $q$ خط بعدی در هر خط ابتدا یک عدد $t_i$ می‌آید و سپس $t_i$ تا عدد که اندیس مالیات‌چی هاست و یک عدد $k_i$ که یعنی آن $t_i$ تا مالیات‌چی در $k_i$ تا از مردم شهر با هم مشترک هستند.

** دقت کنید که اشتراک‌هایی که به شما داده می‌شوند از هم جدا و کاملا مستقل هستند؛ یعنی مثلا اگر مالیاتچی‌های ۱ و ۲ و ۳ در ۵ نفر و مالیاتچی‌های ۱ و ۲ در ۴ نفر با هم اشتراک داشته باشند، طبیعتا این ۴ نفر کاملا مستقل از آن ۵ نفر بوده و هیچ اشتراکی ندارند. **

$1 \le m \le n \le 20$ $1 \le q \le 10$ $2 \le t_i \le n$ $1 \le a_i \le 100$

برای فهم بهتر توضیح نمونه ۱ را بخوانید.

خروجی🔗

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

مثال🔗

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

5 3
15 20 25 30 24
5
2 1 2 7
3 1 2 3 3
2 2 3 2
2 3 4 5
2 4 5 6 

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

68

بهترین حالت این است که مالیات‌چی دوم و چهارم و پنجم را انتخاب کنیم، که از آنجایی که مالیات چی ۴ و ۵ در ۶ نفر باهم مشترک هستند جواب آخر برابرست با ۶ - ۲۰ + ۳۰ + ۲۴

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

3 3
3 3 3
1
3 1 2 3 2

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

5

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

متاسفانه باخبر شدیم که آقای مالیاتچی، به کشور فلان فرار مالیاتی کرده است!

حیف که دیر فهمیدیم وگرنه زودتر فرد مناسبی را جایگزین او میکردیم. از این رو این سوال شسته و رفته خدمت شما:

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

ورودی🔗

در تنها سطر ورودی یک رشته که تنها از حروف کوچک انگلیسی درست شده است آمده است. طول این رشته بین ۱ تا $10^5$ می‌باشد.

خروجی🔗

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

مثال🔗

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

aaa

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

6

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

z

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

1

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

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

بشقاب‌ها دارای اندازه‌های مختلفی هستند و چندین بشقاب با اندازه‌های متفاوت درون یک بسته به ترتیب اندازه (کوچک‌ترین بشقاب در بالا و بزرگ‌ترین بشقاب در پایین) چیده می‌شوند. این مدل چینش را چیدمان مالیاتچی پسند می‌نامیم. شرکت بشقاب‌ها را با چیدمان مالیاتچی پسند از تولیدکنندگان دریافت و با چیدمان مالیاتچی پسند هم صادر می‌کند. برای انجام این کار فقط اجازه‌ی انجام دو عملیات وجود دارد:

• تجزیه: یک بسته بشقاب را می‌توان با برداشتن چند بشقاب از بالای آن و قرار دادن بشقاب‌ها در بسته‌ی جدید، به دو بسته‌ی جدید تجزیه کرد.

• ترکیب: با قرار دادن یک بسته روی بسته‌ی دیگر، می‌توان دو بسته را ترکیب کرد. زمانی اجازه‌ی انجام این‌ کار وجود دارد که پایین ترین بشقاب بسته‌ی بالایی بزرگ‌تر از بالاترین بشقاب بسته‌ی پایینی نباشد. در این صورت بسته‌‌ی به وجود آمده چیدمانِ مالیاتچی پسند دارد.

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

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

ورودی🔗

در خط اول ورودی عدد $n$ آمده است که تعداد بسته‌هایی که باید ترکیب شوند را نشان می‌دهد. در $n$ خط بعدی در هر خط ابتدا عدد $k$ آمده است که تعداد بشقاب‌های درون آن بسته را نشان می‌دهد و سپس به دنبال آن $k$ عدد به صورت غیر نزولی می‌آید که قطر بشقاب‌های این بسته از بالا تا پایین را نشان می‌دهد.

قطر هر بشقاب‌ عددی صحیح و نا منفی و حداکثر ۱۰۰۰۰ است. $1 \le n \le 50$ $1 \le k \le 50$

خروجی🔗

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

مثال🔗

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

2
3 1 2 4
2 3 5

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

5

توضیح نمونه‌ی ۱: در این نمونه ابتدا بسته اول را به دوقسمت (۱و۲) و (۴) و بسته‌ی دوم را به دو قسمت (۳) و (۵) تجزیه می‌کنیم، سپس در حرکت سوم بسته‌ی (۱و۲) را با بسته‌ی (۳) ترکیب، در حرکت چهارم بسته‌ی (۱و۲و۳) را با بسته‌ی (۴) ترکیب و در مرحله‌ی آخر بسته‌ی (۱و۲و۳و۴) را با بسته‌ی (۵) ترکیب می‌کنیم.

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

3
4 1 1 1 1
4 1 1 1 1
4 1 1 1 1

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

2

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

به علت اعتراض فراوان مردم به مالیات، اداره‌ی مالیات نحوه محاسبه‌ی مالیات را عوض کرده است تا مثلا بگوید که به اعتراضات رسیدگی کرده است.

در این محاسبه‌ی جدید مالیات، افراد با توجه به درآمد و سطح سوادشان مالیات می‌دهند. مثلا مالیات شخصی با سطح سوادی $k$ و درآمد $x$ به این صورت حساب می‌شود:

تابع $f(x, k)$ را به این صورت تعریف میکنیم که اگر $x$ زوج باشد $f(x, k) = x / 2$ و اگر $x$ فرد باشد $f(x, k) = x + k$.

حال دنباله‌ی زیر را در نظر بگیرید:

$x, f(x, k), f(f(x, k), k), f(f(f(x, k), k), k), ...$

مقدار مالیات شخصی با درآمد $x$ و سطح سواد $k$ برابر اولین عضو دنباله‌ی بالا است که مقدار آن کمتر یا مساوی $k$ می‌باشد. اندیس این عضو از دنباله را $g(x, k)$ فرض میکنیم.(دنباله از ۰ شماره‌گذاری می‌شود) اگر مرد مالیاتچی از چنین شخصی مالیات بگیرد به اندازه‌ی $g(x, k)$ می‌تواند کارمزد برای خودش بگیرد.

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

مرد مالیاتچی می‌خواهد از یک محله ثروتمند پول بگیرد. تمامی افراد این محله دارای سطح سواد $d$ می‌باشند. میزان درآمد افراد این محله بین $l$ تا $r$ می‌باشد.(دقیقا به ازای هر عدد در این بازه یک نفر است که این درآمد را دارد)

حال به مرد مالیاتچی بگویید که در مجموع او چقدر می‌تواند پول به عنوان کارمزد بسلفد!

ورودی🔗

در تنها سطر ورودی سه عدد $l$، $r$ و $d$ آمده است.

عدد $d$ فرد می‌باشد.

$1 \le d \le 100 \ 000$ $1 \le l \le r \le 10^{16}$

خروجی🔗

در تنها سطر خروجی میزان درآمد مرد مالیاتچی را خروجی دهید.

مثال🔗

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

6 6 1

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

4

توضیح نمونه۱

دنباله‌ی $f(6, 1)$ به این صورت است:

$6, 3, 4, 2, 1, 2, 1, 2, 1, 2, ...$

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

1 5 3

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

4