در انبار شرکت هیولاها، ‎$n$ «دَر»‎ از در اتاق خواب‌های کودکان جهان قرار دارد. دَر ‎$i$‎ام از این دَرها، ‎$h_i$‎ متر ارتفاع دارد ولی ضخامت همه آن‌ها با هم برابر است. انبار شرکت به شکل یک قفسه است که ‎$k$‎ طبقه دارد و در طبقه‌ی ‎$j$‎ام آن، ‎$n_j$‎ در جا می‌شود (همان‌طور که گفته شد، ضخامت درها با هم برابر است)؛ ولی توجه به این نکته مهم است که ارتفاع طبقه‌ی ‎$j$‎ام ‎$l_j$‎ متر است؛ در نتیجه تنها می‌توان درهایی را در این طبقه از انبار قرار داد که ارتفاعی کم‌تر یا مساوی با ارتفاع این طبقه داشته باشند. هدف مدیر شرکت هیولاها، قرار دادن بیش‌ترین تعداد دَر در داخل این قفسه‌ها (صرفاً به‌صورت کاملاً عمودی) می‌باشد. ‎

برنامه‌ای بنویسید که

• $n$‎ تعداد دَرها و ‎$h_i$‎ ارتفاع آن‌ها را از ورودی‎ بخواند.
• $k$‎ تعداد طبقه‌های قفسه‌ی انبار و ‎$l_j$‎ ارتفاع و ‎$n_j$‎ گنجایش هر یک را از ‎ورودی‎ بخواند.
• ‎ بیش‌ترین تعداد دَری که در داخل قفسه‌ی انبار جا می‌شود را در ‎خروجی‎ بنویسد.

• در سطر اول ورودی، به ترتیب ‎$n$‎ و ‎$k$‎ آمده است‎.
• در سطر بعدی، ‎$n$‎ عدد آمده که عدد ‎$i$‎ ام، ‎$h_i$‎ ارتفاع دَر ‎$i$‎ام را نشان می‌دهد. ‎
• در ‎$k$‎ سطر بعدی، در هر سطر به ترتیب دو عدد ‎$l_j$‎ و ‎$n_j$‎ نوشته شده است.
• ‎ $1 \leq n,k \leq 10^5$‎
• تمام اعداد ورودی طبیعی و مثبت می‌باشند.
• در ‎$30$‎% تست‌ها ‎$1 \leq n,k \leq 100$‎ می‌باشد.

در نتها سطر خروجی بیش‌ترین تعداد دَر که در داخل قفسه‌های انبار جا می‌شود را بنویسید.

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

• سوال بعد
• سوال قبل