+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در شهر گلرنگ $n$ خیابان افقی یک‌طرفه شمال به جنوب و $m$ خیابان عمودی یک‌طرفه غرب به شرق وجود دارد. همانطور که انتظار داریم تمام خیابان‌های عمودی با یکدیگر و تمام خیابان‌های افقی نیز با یکدیگر موازی‌اند و همچنین هر خیابان افقی با تمام خیابان‌های عمودی متقاطع است. تعدادی تپسی داریم که می‌خواهند این خیابان‌ها را از ابتدا تا انتها طی کنند. در هر تقاطع یک چراغ راهنمایی وجود دارد که در هر لحظه برای یکی از دو خیابان تقاطع سبز و برای دیگری قرمز است. هر کدام از چراغ‌ها یک عدد به نام $x$ دارند که با شروع از لحظه صفر برای خیابان افقی آن تقاطع به طور متناوب $x$ ثانیه سبز و سپس $x$ ثانیه قرمز اند. همچنین هر تقاطع یک عدد $y$ نیز دارد که نشان می‌دهد در در هر ثانیه در آن تقاطع حداکثر $y$ تپسی می‌توانند عبور کنند.  در ابتدای هر خیابان تعداد مشخصی تپسی وجود دارند که همزمان با شروع از ثانیه ۰ حرکت کرده و می‌خواهند به انتهای خیابان خودشان برسند. طی کردن طول هر خیابان در شهر گلرنگ انقدر سریع است که می‌توان گفت ۰ ثانیه زمان نیاز دارد. اما در این شهر عبور از تقاطع‌ها زمان نیاز دارد. هر تپسی در صورتی می‌تواند از یک تقاطع عبور کند که چراغ قرمز آن تقاطع برای آن خیابان سبز باشد. دقت کنید در هر تقاطع میزان مشخصی تپسی در هر ثانیه می‌تواند عبور کند، پس ممکن است تپسی‌ها پشت چراغ قرمز تقاطعی منتظر بمانند و چندین بار سبز شدن چراغ را مشاهده کنند تا در نهایت بتوانند از تقاطع عبور کنند. شهردار شهر گلرنگ از شما می‌خواهد آخرین ثانیه‌ای که یک تپسی به انتهای خیابان خود می‌رسد را بگویید. # ورودی در سطر اول ورودی دو عدد $n$ و $m$ داده می‌شود که به ترتیب نشان‌دهنده تعداد خیابان‌های افقی و عمودی است. سپس در خط دوم $n$ عدد، تعداد تپسی‌های خیابان‌های افقی و در خط بعدی $m$ عدد به عنوان تعداد تپسی‌های خیابان‌های عمودی داده می‌شود. سپس در $n$ خط بعدی در هر خط $2m$ عدد نشانگر اطلاعات چهارراه‌های خیابان‌های افقی است. در هر خط به ترتیب $m$ جفت $x_i$ و $y_i$ داده می‌شود که $x_i$ بیانگر میزان ثانیه سبز برای چراغ $i$ در این خیابان است و $y_i$ برابر حداکثر تعداد تپسی ای است که در یک ثانیه از این چهارراه می‌تواند عبور کند. $$1 \leq n, m, y_i \leq 500$$$$0 \leq x_i\leq 1,000,000,000$$ $$\sum_{i = 0}^{i = n} y_i + \sum_{i = 0}^{i = m} y_i \leq 500$$ # خروجی در تنها سطر خروجی ثانیه‌ای که در پایان آن، آخرین تپسی به مقصد می‌رسد را چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 1 1 6 8 7 4 ```` ## خروجی نمونه ۱ ``` 8 ```` ## ورودی نمونه ۲ ``` 3 2 35 7 4 160 104 4 7 7 1 7 5 7 2 9 7 3 9 ```` ## خروجی نمونه ۲ ``` 208 ````

حل سؤال در بانک سؤالات