আজ লুকের জন্মদিন। মিস্টার ফিল ডামফি(লুকের বাবা) এ উপলক্ষ্যে তার জন্যে একটি জন্মদিনের পার্টি রেখেছেন এবং লুককে কিছু গিফট কিনে দেবেন বলে ঠিক করেছেন। তো তিনি ইন্টারনেট ঘেটে নিচের তথ্য গুলো বের করেছেন।
শহরের দোকানগুলোতে M সংখ্যক বিভিন্ন ধরনের গিফট আইটেম আছে। আইটেমগুলোতে ক্রমান্বয়ে 1 থেকে M নম্বর দেয়া আছে। সেখানে N সংখ্যক দোকান আছে যেখানে এই আইটেম গুলো পাওয়া যায়। কিন্তু একটি দোকানে সব ধরনের আইটেম নাও থাকতে পারে। কোন দোকানে কি আইটেম আছে তার একটি লিস্ট তাঁর কাছে আছে।
মিস্টার ফিল তার কাজে সাহায্যের জন্যে N জন কর্মচারী যোগাড় করেছেন। তিনি তার প্রত্যেক কর্মচারীকে নির্দিষ্ট একটি দোকানে পাঠাবেন । কোন দোকানেই একজনের বেশি কর্মচারী যাবে না। i-তম কর্মচারী সর্বোচ্চ Ci সংখ্যক আইটেম কিনতে পারবে তাকে বরাদ্দকৃত দোকান থেকে। তারা নিজের বরাদ্দকৃত দোকান ছাড়া অন্য কোন দোকান থেকে কোন আইটেম কিনতে পারবে না। প্রত্যেক কর্মচারী প্রতিটি পণ্য একবার করেই কিনতে পারবে। আবার, দুজন কর্মচারী একই পণ্য কিনতে পারবে না। মিস্টার ফিল এমনভাবে তার কর্মচারীদের দোকান বরাদ্দ করতে চান যাতে তিনি সর্বোচ্চ সংখ্যক গিফট কিনতে পারেন।
Input
প্রথম লাইনে একটি পূর্ণসংখ্যা T দেয়া থাকবে , যা টেস্ট কেস এর সংখ্যা নির্দেশ করবে।
প্রত্যেকটি টেস্ট কেস এর প্রথম লাইনে দুটি পূর্ণসংখ্যা N ও M থাকবে।
দ্বিতীয় লাইনে N সংখ্যক পূর্ণসংখ্যা থাকবে, Ci (0<= Ci <=M) যা i-তম কর্মচারী কতটি আইটেম কিনতে পারবে তা নির্দেশ করবে।
তারপর বাইনারী ম্যাট্রিক্স A যার সাইজ হচ্ছে (NxM) আসবে। সারির সংখ্যা দোকানের সংখ্যা নির্দেশ করে এবং কলামগুলো আইটেমের সংখ্যা নির্দেশ করে। Aij যদি 1 হয়, তাহলে j-তম আইটেম i-তম দোকানে আছে, তাছাড়া আইটেমটি নেই।
স্কোরিং
সাবটাস্ক ১ (২০ পয়েন্ট):
1 ≤ T ≤ 15 N = 2 1 ≤ M ≤ 100000
সাবটাস্ক ২ (৪০ পয়েন্ট):
1 ≤ T ≤ 5 3 ≤ N ≤ 5 1 ≤ M ≤ 1000
সাবটাস্ক ৩ (৪০ পয়েন্ট):
1 ≤ T ≤ 5 3 ≤ N ≤ 5 1 ≤ M ≤ 100000
Output
প্রত্যেক টেস্টকেসের জন্য বলতে হবে যে, মিস্টার ফিল সর্বোচ্চ কতগুলো আইটেম কিনতে পারবে।
Samples
| Input | Output |
|---|---|
1 3 5 1 1 2 10010 00110 01010 | 4 |
| Input | Output |
|---|---|
1 4 6 1 1 2 2 000101 100011 000111 111100 | 6 |
