Limits 1s, 512 MB

Toph স্কুল ও কলেজ এ দুটি সেকশন আছে, সেকশন A এবং সেকশন B।

সম্প্রতি দুই সেকশন এর শিক্ষার্থীরা নিজেদের মধ্যে মুছুনির মত ছোট্ট একটি বিষয় নিয়ে দ্বন্দ্বে জড়িয়ে পড়ে।

যেহেতু এইসব স্কুল এর নিয়ম পরিপন্থী, তাই স্কুল কর্তৃপক্ষ শিক্ষার্থীদের শাস্তি দেয়ার সিদ্ধান্ত নেয়।

শাস্তি হিসেবে কিছু শিক্ষার্থী কে বের করে দেয়া হবে। এখন কাদের বের করে দেয়া উচিত এই সিদ্ধান্ত নেয়ার জন্যে শিক্ষকদের কাছ থেকে ভোট নেয়া হবে।

প্রত্যেক শিক্ষক 2 জন শিক্ষার্থীর কথা উল্লেখ করবে। একজন যাকে বের করে দেয়া উচিত নয়, আরেকজন যাকে বের করে দেয়া উচিত। যেহেতু কোনো শিক্ষকই উভয় সেকশন এ ক্লাস নেয় না তাই তার নিজের সেকশন এর শিক্ষার্থীদের উপর একটা আলাদা টান রয়েছে।

প্রত্যেক শিক্ষক এ তার ভোটে নিজের সেকশন এর একজনকে রাখার জন্যে এবং অপর সেকশন এর একজন কে বের করার জন্যে সুপারিশ করেছে।

কর্তৃপক্ষ এমন ভাবে সিদ্ধান্ত নিবে যেনো সর্বোচ্চ সংখ্যক শিক্ষক কে খুশি করা যায়।

একজন শিক্ষক তখন ই খুশি হবে যদি তার উভয় সুপারিশ বাস্তবে রূপান্তরিত হয়।

তুমি কি বলতে পারো যে সর্বোচ্চ কতজন শিক্ষক কে একসাথে খুশি করা যাবে?

Input

শুরুতে তোমাকে একটা পূর্ণ সংখ্যা T(0 < T ≤ 50) দেয়া হবে. যা টেস্ট কেস এর সংখ্যার নির্দেশক।

প্রতিটি টেস্ট কেস তিনটি পূর্ণসংখ্যা a(0 < a ≤ 100), b(0 < b ≤ 100) and n (0 ≤ n ≤ 500) দিয়ে শুরু হয়। a নির্দেশ করে A সেকশন এর শিক্ষার্থী সংখ্যা, b নির্দেশ করে B সেকশন এর শিক্ষার্থী সংখ্যা আর n নির্দেশ করে মোট শিক্ষকের সংখ্যা যারা ভোট দিয়েছেন।

পরবর্তী n টি লাইন এ শিক্ষকদের ভোট এর বর্ননা রয়েছে। প্রথমে বলা হবে উনি কোন সেকশন এ ক্লাস নেন। তারপর বলা হবে উনি নিজের সেকশন এর কতো নম্বর শিক্ষার্থীকে রাখার জন্যে এবং অপর সেকশন এর কতো নম্বর শিক্ষার্থী কে বের করে দেয়ার সুপারিশ করেছেন।

A সেকশন এর শিক্ষার্থীদের 1 থেকে a পর্যন্ত আলাদা আলাদা নম্বর রয়েছে এবং B সেকশন এর শিক্ষার্থীদেরও 1 থেকে b পর্যন্ত নম্বর রয়েছে। এটা নিশ্চিত যে শিক্ষক এর ভোট p, q হলে উনার নিজের সেকশন এ অবশ্যই অন্ততঃ p জন এবং অপর সেকশন এ অবশ্যই অন্ততঃ q জন শিক্ষার্থী রয়েছে।

Subtask Details :

Subtask 1, 10% পয়েন্ট এর জন্যে : (a+b ≤ 8 and n ≤ 8)

Subtask 2, 20% পয়েন্ট এর জন্যে : (a+b ≤ 32 and n ≤ 16)

Subtask 3, 40% পয়েন্ট এর জন্যে : (a+b ≤ 32 and n ≤ 32)

Subtask 4, 100% পয়েন্ট এর জন্যে : Original Constraints.

Output

প্রতিটি টেস্ট কেস এর জন্যে একটা সংখ্যা প্রিন্ট করো যা নির্দেশ করে সর্বোচ্চ কতজন শিক্ষককে একসাথে খুশি করা সম্ভব।

Sample

InputOutput
2
5 5 3
B 1 2
A 2 4
A 1 1
2 2 4
A 1 1
B 1 2
A 2 2
B 2 1
2
2

Submit

Login to submit.

Statistics

57% Solution Ratio
YouKnowWhoEarliest, Jul '20
nusuBotFastest, 0.0s
YouKnowWhoLightest, 655 kB
YouKnowWhoShortest, 1822B
Toph uses cookies. By continuing you agree to our Cookie Policy.