کار حداکثری، حقوق حداقلی


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

کارل مارکس، بنیانگذار فقید کمونیسم، به دنبال بیشترین بهره‌وری از افراد با بهره‌مند کردن آن‌ها از حداقل حقوق است. او می‌داند که یکسری کار در جامعه با سختی بخصوص وجود دارد. از طرفی جامعه تعدادی نیروی کار دارد که در ماه اگر بیش از حد مشخص سختی بکشند، تلف می‌شوند. او همچنین توانایی هر کس در هر کار را نیز شناسایی کرده‌است و به عبارت دیگر اگر سختی یک کار hh و توانایی یک فرد در آن ss باشد، hs\frac{h}{s} ساعت طول می‌کشد تا آن شخص به تنهایی آن کار را تمام کند و متحمل hh واحد سختی شود. توجه کنید که هر فرد می‌تواند کل یک کار و یا تنها بخشی از آن را انجام دهد و به میزان آن بخش سختی و طول کشیدنش خواهد بود.

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

ورودی🔗

در سطر اول jj تعداد کارها می‌آید و در سطر بعد jj عدد صحیح می‌آید که عدد iiام hih_i نشانگر سختی کار شماره ii است.

در سطر سوم nn تعداد افراد می‌آید و در سطر بعد nn عدد صحیح با فاصله می‌آید که عدد iiام mim_i نشانگر حداکثر سختی است که می‌تواند در ماه کار کند.

در سطر iiام از jj سطر بعد nn عدد صحیح می‌آید که عدد jjام si,js_{i,j} نشانگر توانایی فرد jj در کار ii است. 1j,hi,n,mi,si,j1001 \le j, h_i, n, m_i, s_{i, j} \le 100 تضمین می‌شود که شکلی از تقسیم کار وجود دارد که تمامی کارها کامل انجام شود و هیچ فرد بیش از حداکثر ظرفیتش کار نکند.

خروجی🔗

تنها یک عدد که نشانگر کمینه مجموع ساعات کاری افراد برای انجام تمام کارها است را خروجی دهید. پاسخ شما زمانی درست در نظر گرفته خواهد شد که اختلاف آن با پاسخ واقعی حداکثر 10610^{-6} باشد.

مثال🔗

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

1
10
2
6 7
4 1
Plain text

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

5.5
Plain text

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

3
7 9 11
2
10 17
5 4
8 5
3 2
Plain text

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

7.3833333333333
Plain text

در مثال اول، چنانچه نفر اول 35\frac{3}{5} کار را انجام دهد و نفر دوم 25\frac{2}{5} کار را، به ترتیب باید ۱.۵ و ۴ ساعت زمان صرف کنند. توجه کنید که نفر اول با انجام 35\frac{3}{5} کار متحمل ۶ سختی می‌شود و بیش از این نمی‌تواند کار کند.

در مثال دوم، نفر اول کافی است که همه ۱۰ ظرفیت سختی رو خود را برای کار سوم بگذارد و بقیه کارها را به نفر دوم بسپارد.