+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۱۲۸ مگابایت ***** در یک صف $n$ سرباز با شماره‌های ۱ تا $n$ ایستاده‌اند. سرباز $i$ام در ابتدا $S_i$ نشان لیاقت(مدال) روی سینه‌اش دارد. طی مراسمی $m$ ژنرال می‌خواهند به این سربازها مدال‌های جدید بدهند. می‌دانیم ژنرال $i$ام به سربازانی که شماره‌شان در بازه‌ی $\left[ a_i, b_i\right]$ باشد مدال خواهد داد. هم‌چنین می‌دانیم اگر بازه‌های دو ژنرال مثل $x$ و $y$ با هم اشتراک داشته باشند، نمی‌توان دو سرباز مثل $u$ و $v$ یافت که $u$ فقط از $x$(و نه از $y$) و $v$ فقط از $y$(و نه از $x$) مدال گرفته باشد. مجری مراسم می‌خواهد زیرمجموعه‌ای از ژنرال‌ها را به مراسم دعوت کند که در پایان مراسم(پس از اهدای مدال‌ها) تعداد سربازهایی که فرد مدال دارند(با احتساب مدال‌های اوّلیّه) بیشینه شود. این مقدار بیشینه را پیدا کنید! شما باید به ازای $t$ سناریو جواب را پیدا کنید. # ورودی در سطر اوّل ورودی عدد طبیعی $t$ آمده است. به ازای هر سناریو، در سطر اوّل $n$ و در سطر پس از آن $S_i$ها به ترتیب آمده‌اند. سپس در سطر بعد $m$ آمده است؛ در سطر بعد $2m$ عدد نوشته شده است که عدد $2i - 1$ام، $a_i$ و عدد $2i$ام برابر $b_i$ خواهد بود. $$1\leq t \leq 20$$ به طور کلّی $1\leq n,m \leq 100\ 000$ ولی در ۳۰ درصد از تست‌ها شرط $1\leq n,m \leq 2\ 000$ برقرار خواهد بود. $$1 \leq a_i \leq b_i \leq n$$ تمامی اعداد ورودی صحیح، نامنفی و حداکثر برابر $10^9$ خواهند بود. # خروجی جواب هر سناریو(حداکثر تعداد سربازها با شرایط مذکور) را به ترتیب در خط‌های جدا از هم بنویسید. # مثال ## ورودی نمونه ``` 2 3 8 9 0 3 1 3 1 1 1 1 4 7 6 8 2 3 1 4 1 1 4 4 ``` ## خروجی نمونه ``` 2 4 ```

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