- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
در اداره مالیات \(n\) مالیاتچی وجود دارد.
مالیاتچی \(i\) ام میتواند از \(a_i\) نفر خاص در شهر مالیات بگیرد.
متاسفانه به علت کمبود بودجه اداره مالیات، ما برای سال بعد فقط میتوانیم \(m\) تا از مالیاتچیها را نگه داریم، حالا از شما میخواهیم به رییس اداره مالیات بگویید در صورتی که به بهترین شکل این \(m\) نفر را انتخاب کند حداکثر از چند نفر میتواند مالیات بگیرد.
همچنین میدانیم بعضی از اشخاصی که بعضی از مالیاتچیها میتوانند از آنها مالیات بگیرند مشترک هستند.
مثلا مالیات چی اول و دوم هر کدام میتوانند به ترتیب از ۷ و ۸ نفر در شهر مالیات بگیرند اما ۳ نفر از این افراد مشترک است، پس چنانچه بخواهیم دو نفر مالیاتچی نگه داریم و این دو نفر را انتخاب کنیم ما از ۱۲ نفر میتوانیم مالیات بگیریم نه از ۱۵ نفر.
برای فهم بهتر سوال بخش ورودی را بخوانید.
ورودی
در یک خط \(n\) به شما داده میشود که تعداد مالیاتچیهاست و سپس \(m\) که تعداد مالیاتچیهایی است که برای سال بعد میتوانیم داشته باشیم.
سپس در خط بعد \(n\) عدد که \(a_i\) هاست به شما داده میشود.
در خط سوم \(q\) به شما داده میشود و در \(q\) خط بعدی در هر خط ابتدا یک عدد \(t_i\) میآید و سپس \(t_i\) تا عدد که اندیس مالیاتچیهاست و یک عدد \(k_i\) که یعنی آن \(t_i\) تا مالیاتچی در \(k_i\) تا از مردم شهر با هم مشترک هستند.
** دقت کنید که اشتراکهایی که به شما داده میشوند از هم جدا و کاملا مستقل هستند؛ یعنی مثلا اگر مالیاتچیهای ۱ و ۲ و ۳ در ۵ نفر و مالیاتچیهای ۱ و ۲ در ۴ نفر با هم اشتراک داشته باشند، طبیعتا این ۴ نفر کاملا مستقل از آن ۵ نفر بوده و هیچ اشتراکی ندارند. **
\[ 1 \le m \le n \le 20\] \[ 1 \le q \le 10\] \[ 2 \le t_i \le n\] \[ 1 \le a_i \le 100\]
برای فهم بهتر توضیح نمونه ۱ را بخوانید.
خروجی
در یک خط بیشینهی تعداد نفراتی که میشود سال بعد از آنها مالیات گرفت را چاپ کنید.
مثال
ورودی نمونه ۱
5 3
15 20 25 30 24
5
2 1 2 7
3 1 2 3 3
2 2 3 2
2 3 4 5
2 4 5 6
خروجی نمونه ۱
68
بهترین حالت این است که مالیاتچی دوم و چهارم و پنجم را انتخاب کنیم، که از آنجایی که مالیات چی ۴ و ۵ در ۶ نفر باهم مشترک هستند جواب آخر برابرست با ۶ - ۲۰ + ۳۰ + ۲۴.
ورودی نمونه ۲
3 3
3 3 3
1
3 1 2 3 2
خروجی نمونه ۲
5