فهرست مندرجات
رأی‌گیری
وزیر آموزش و پرورشِ «گل‌تپه» قصد دارد از «باشگاه دانش‌پژوهان جوانِ گل‌تپه« دیدن کند و در مراسم صبح‌گاهی برای دانش‌پژوهان سخنرانی کند! در مراسم صبح‌گاهی، همواره دانش‌پژوهان در $n$ صفِ $m$نفره قرار می‌گیرند و این بار با توجه به طولانی‌بودن مدت سخنرانی، قرارست سر جای خود بر روی زمین بنشینند. در انتها، قرارست یک رأی‌گیری در مورد وضع غذای باشگاه انجام شود و در صورتی که کم‌تر از $k$ نفر به خوب بودن وضع غذا رأی بدهند، وزیر ناراحت می‌شود!
رأی‌گیری به این صورت است که پس از پرسشِ وزیر درباره‌ی خوب بودن غذا، کسانی که به‌نظرشان وضع غذا خوب است از روی زمین برخواسته و سر پا می‌ایستند؛ اما با توجه به قدِ کوتاهِ وزیر، اگر کسی در یک صف سر پا بایستد، وزیر فکر می‌کند که تمام افراد پشت سر او هم ایستاده‌اند و نتیجتاً موافق وضع کنونی هستند!
رئیس باشگاه که دوست ندارد وزیر ناراحت شود، از کلیّه دانش‌پژوهان می‌خواهد که در زمان رأی‌گیری بایستند؛ اما پس از مطرح‌کردن این درخواست متوجه می‌شود که هر کدام از دانش‌پژوهان در ازای ایستادن، مقداری پول می‌خواهند! پس از اندکی تفکر او با خود می‌اندیشد که لازم نیست به همه دانش‌پژوهان پول بدهد و برخواستن برخی از دانش‌پژوهانِ منصف‌تر (که هرکدام نظر مثبت تمام پشت‌سری‌هایش را نیز برای وزیر به ارمغان می‌آورد) برای داشتن $k$ رأی مثبت کافی‌ست.
به رئیس باشگاه کمک کنید تا با پرداخت کم‌ترین پول به دانش‌پژوهان، کاری کند که وزیر ناراحت نشود.
ورودی
- در سطر اوّل ورودی عدد $n$ (تعداد صف‌ها) و بعد از آن، عدد $m$ (تعداد افراد هر صف) آمده است.
- پس از آن، در سطر دوم تنها عدد $k$ آمده است.
- در $n$ سطر بعدی، در هر سطر $m$ عدد آمده است که این اعداد پول درخواستی دانش‌پژوهان آن صف به‌ترتیب (از چپ به راست) از جلوی صف است. به عبارت دیگر، هر سطر یک صف را توصیف می‌کند و وزیر در ضلع سمت چپ جدول ایستاده است.
- $0 \leq k \leq n\times m \leq 10,000$؛ علاوه بر این در $70$ درصد تست‌ها، $n\times m \leq 5,000$ است.
- پول‌های درخواستی در بازه‌ی $[0, 200,000]$ هستند و نتیجتاً جواب در تایپ
int جا می‌شود.
خروجی
در تنها سطر خروجی، کم‌ترین بودجه‌ی موردنیاز رئیس باشگاه برای راحت‌گذاشتن خیال وزیر را بنویسید.
محدودیت‌ها
- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
ورودی و خروجی نمونه
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
