شهر گلرنگ


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

در شهر گلرنگ nn خیابان افقی یک‌طرفه شمال به جنوب و mm خیابان عمودی یک‌طرفه غرب به شرق وجود دارد. همانطور که انتظار داریم تمام خیابان‌های عمودی با یکدیگر و تمام خیابان‌های افقی نیز با یکدیگر موازی‌اند و همچنین هر خیابان افقی با تمام خیابان‌های عمودی متقاطع است. تعدادی تپسی داریم که می‌خواهند این خیابان‌ها را از ابتدا تا انتها طی کنند.

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

توضیح تصویر

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

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

ورودی🔗

در سطر اول ورودی دو عدد nn و mm داده می‌شود که به ترتیب نشان‌دهنده تعداد خیابان‌های افقی و عمودی است. سپس در خط دوم nn عدد، تعداد تپسی‌های خیابان‌های افقی و در خط بعدی mm عدد به عنوان تعداد تپسی‌های خیابان‌های عمودی داده می‌شود.

سپس در nn خط بعدی در هر خط 2m2m عدد نشانگر اطلاعات چهارراه‌های خیابان‌های افقی است. در هر خط به ترتیب mm جفت xix_i و yiy_i داده می‌شود که xix_i بیانگر میزان ثانیه سبز برای چراغ ii در این خیابان است و yiy_i برابر حداکثر تعداد تپسی ای است که در یک ثانیه از این چهارراه می‌تواند عبور کند.

1n,m,yi5001 \leq n, m, y_i \leq 5000xi1,000,000,0000 \leq x_i\leq 1,000,000,000 i=0i=nyi+i=0i=myi500\sum_{i = 0}^{i = n} y_i + \sum_{i = 0}^{i = m} y_i \leq 500

خروجی🔗

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

مثال‌ها🔗

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

1 1
6
8
7 4
Plain text

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

8
Plain text

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

3 2
35 7 4
160 104
4 7 7 1
7 5 7 2
9 7 3 9
Plain text

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

208
Plain text