মাইন্ড ফ্লেয়ার নামক ছায়া দানব আবারও হকিন্স শহরে আক্রমণ করেছে। সাইকোকাইনেটিক সক্ষমতা সম্পন্ন মেয়ে এলের বিরুদ্ধে লড়াই করার জন্য মাইন্ড ফ্লেয়ার এবার পুরো প্রস্তুতি নিয়েছে। এই প্রস্তুতি নেওয়া সত্ত্বেও, তিনি বুঝতে পারেন যে তিনি এলকে মোটেও পরাজিত করতে পারবেন না। সুতরাং, সমস্ত পরিস্থিতি পর্যবেক্ষণ ও বিশ্লেষণের পরে, তিনি একটি বিকল্প পরিকল্পনা তৈরি করেছেন। তিনি তার নিজের দুনিয়ায় একজন প্রবলেম সেটার বিশেষজ্ঞ অনুসন্ধান করে বের করেছেন। এই প্রবলেম সেটার তার জন্য একটি নতুন সমস্যা সেট করেছে। এর পর, মাইন্ড ফ্লেয়ার এলকে সমস্যাটি বলে বলেছেন যে এল যদি যথাসময়ে সমস্যার সমাধান না করতে পারেন তবে তিনি পুরো শহরটি ধ্বংস করে দেবেন। এল সমস্যা সমাধানের জন্য প্রাণপ্রণ চেষ্টা করছে। তবে তিনি যেহেতু ভাল সমস্যা সমাধানকারী নন, তাই সমস্যার দ্রুত সমাধান তিনি খুঁজে পান নি। তার কোড অসীম সময়ের জন্য চলে এবং কোনও আউটপুট দেয় না। হকিন্সের পুলিশ প্রধান জিম হপার এলকে সাহায্য করার জন্য তোমাকে নিয়োগ দিয়েছে। এখন তোমার কাজ হল এলকে সমস্যা সমাধানে সহায়তা করা এবং হকিন্স শহরটিকে মাইন্ড ফ্লেয়ারের আক্রমণ থেকে বাঁচানো।
এলকে দেওয়া সমস্যাটি হ'ল:
তোমাকে দুটি লিস্ট A, B এবং একটি পূর্ণসংখ্যা K দেওয়া হবে। B লিস্টের প্রতিটি পূর্ণসংখ্যা Bi এর জন্য, অরিজিনাল লিস্ট A-র এমন একটি বৃহত্তম সংখ্যা Ag খুঁজে বের কর, যা Bi এর চেয়ে ছোট । Bi এর চেয়ে ছোট কোনো সংখ্যা অরিজিনাল লিস্ট A-তে না থাকলে, ধর, Ag = 0। এরপর (Bi + Ag) কে K বার আপডেটিং লিস্ট A-র শেষে সংযুক্ত কর। সর্বশেষ আপডেটেড লিস্ট A কে লিস্ট C বলা হয়।
উদাহরণ স্বরূপ:
A = [2, 93, 81], B = [100, 1] এবং K = 2 হলে উপরের সমস্ত ক্রিয়াকলাপ করার পর লিস্ট C হবে [2, 93, 81, 193, 193, 1, 1]।
ধর, C লিস্টের একটি পূর্ণসংখ্যা Ci এর জন্য, x হল B লিস্ট থেকে প্রাপ্ত এমন পূর্ণসংখ্যাগুলোর সর্বাধিক সংখ্যা, যেসব পূর্ণসংখ্যাগুলোর যোগফল Ci এর সমান বা ছোট। লিস্ট C এর প্রতিটি পূর্ণসংখ্যা Ci এর জন্য x গণনা কর এবং সকল x এর যোগফল আউটপুট হিসেবে দেখাও।
Input
ইনপুট শুরু হবে একটি পূর্ণসংখ্যা T, টেস্টকেসের সংখ্যা দিয়ে।
প্রতিটি কেসের ক্ষেত্রে, প্রথম লাইনে থাকবে 3 টি পূর্ণসংখ্যা N, M, K - লিস্ট A-র আকার, লিস্ট B-র আকার এবং পূর্ণসংখ্যা K।
পরবর্তী লাইনে N সংখ্যক পূর্ণসংখ্যা, A লিস্টের পূর্ণসংখ্যাসমূহ Ai থাকবে।
প্রতিটি কেসের শেষ লাইনে Mসংখ্যক পূর্ণসংখ্যা, B লিস্টের পূর্ণসংখ্যাসমূহ Bi দেওয়া থাকবে।
সীমাবদ্ধতা:
1 <= T <= 10
1 <= N <= 105
1 <= M <= 105
1 <= K <= 100
1 <= Ai <= 5 * 105
1 <= Bi <= 5 * 105
10 পয়েন্টের জন্য: 1 <= N <= 102, 1 <= M <= 102
40 পয়েন্টের জন্য: 1 <= N <= 5 * 104, 1 <= M <= 2 * 104
100 পয়েন্টের জন্য: 1 <= N <= 105, 1 <= M <= 105
Output
প্রতিটি কেসের ক্ষেত্রে, সমস্যার বিবৃতিতে বর্ণিত সকল x এর যোগফল একটি লাইনে আউটপুট হিসেবে দেখাও।
Sample
| Input | Output |
|---|---|
1 3 2 2 2 93 81 100 1 | 9 |
