মিঃ হিকিকো সম্প্রতি তাঁর ফোনে একটি অদ্ভুত গেম ডাউনলোড করেছেন। গেমটি বেশ আকর্ষণীয় তবে তিনি এতই অলস যে তিনি গেমটি প্রতিটি লেভেল খেলতে চান না। তাই তিনি একটি কোড লেখার সিদ্ধান্ত নিয়েছেন, যেই কোডটি গেমের সবগুলো লেভেল শেষ করবে। তার অলসতা নিয়ে আরেকটু বলি। তিনি এতোই অলস যে, তিনি কোডটি ও নিজে নিজে লিখতে চান না। তাই তিনি চান যে কেউ তাকে সাহায্য করুক। তুমি কি তাকে সাহায্য করতে পারবে?
এই গেমের নিয়মগুলো খুব ই সহজ। প্রথমে তোমাকে একটি গ্রিড দেওয়া হবে, যার n টি সারি এবং m টি কলাম রয়েছে। গ্রিডের প্রতিটি ঘরে একটি করে পয়েন্ট থাকবে।
তোমাকে প্রথম সারি থেকে শুরু করতে হবে। তুমি প্রথমে প্রথম সারির যেকোন একটা ঘর সিলেক্ট করবে। তারপর এই ঘরসহ পরপর k টা ঘর সিলেক্ট করবে, এবং এই ঘরগুলোতে থাকা পয়েন্ট গুলো নিবে। তারপর তোমাকে এই সারির সিলেক্ট করা যেকোনো ঘর থেকে পরবর্তী সারির যেকোনো একটি ঘরে লাফ দিতে হবে যেনো ঘরগুলোর ব্যাবধান l এর সমান বা তার কম হয়। এইখানে ব্যাবধান বলতে দুটি ঘরের কলাম নাম্বারের পার্থক্য বুঝানো হয়েছে। যদি আমরা ঘর১,১ থেকে ঘর২,৪ এ লাফ দিয়ে যাই, তাহলে ব্যাবধান হিবে ।১ - ৪। = ৩। লাফ দিয়ে যাওয়ার পর, তোমাকে এই সারির ও পরপর k টা ঘর সিলেক্ট করতে হবে, যেন অবশ্যই এদের মধ্যে লাফ দিয়ে আসা ঘরটা থাকে। এরপর তুমি এই ঘরগুলো পয়েন্ট গুলো ও নিবে এবং আবার পরের সারিতে তে একটা লাফ দিবে। এভাবেই তোমাকে লাফ দিয়ে দিয়ে পয়েন্টগুলো নিতে হবে যতক্ষন পর্যন্ত না তুমি n তম সারিতে পৌছাচ্ছ।
তুমি প্রথম সারির যেকোনো ঘর থেকে ই শুরু করতে পারো। যখন তোমার সবগুলো সারি লাফানো শেষ হইয়ে যাবে, তুমি সর্বোচ্চ কতো মোট পয়েন্ট তুলতে পারবে?
ইনপুটে মোট T (1 ≤ T ≤ 10) টি টেস্ট কেস থাকবে।
প্রতিটি কেসের প্রথম লাইনে n, m, k (1 ≤ k ≤ m), l (0 ≤ l < m) এর মান দেওয়া থাকবে।
পরবর্তীতে গ্রিড টা দেওয়া হবে। গ্রিডের প্রতিটি ঘরের পয়েন্ট 0 থেকে 106 পর্যন্ত হতে পারে।
প্রতিটি টেস্ট কেসের জন্য, তুমি সর্বোচ্চ কতো মোট পয়েন্ট তুলতে পারব তা প্রিন্ট করো।
Input | Output |
---|---|
1 3 6 2 2 2 1 3 0 2 4 5 5 4 2 5 4 10 3 5 4 2 4 | 28 |
Solution for the Sample Case: |