- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
کشی \(n\) رشته باینری به طول \(m\) دارد. در هر عملیات میتواند یکی از این رشتهها را انتخاب کرده و پیشوندی از آن را برعکس کند. (کاراکترهای 0 را به 1 و 1 را به 0 تبدیل کنیم.)
او میخواهد همه این رشتهها را باهم برابر کند. شما باید برای \(T\) سناریوی مختلف، کمترین عملیات لازم برای رسیدن به این هدف را پیدا کنید.
ورودی
در سطر اول ورودی عدد صحیح و مثبت \(T\) آمده است که نشان دهندهی تعداد سناریو هایی است که شما باید به آنها پاسخ دهید. \[1 \leq T \leq 1000\]
در سطر اول هر سناریو، دو عدد صحیح و مثبت \(n\) و \(m\) که با یک فاصله از هم جدا شدهاند؛ آمده است. \[1 \leq n \cdot m \leq 100 \, 000\] در \(n\) سطر بعدی هر سناریو، در هر سطر یک رشته به طول \(m\) آمده است.
تضمین میشود جمع تعداد کاراکترهای رشتهها از \(100 \, 000\) بیشتر نمیشود.
خروجی
خروجی برنامه شامل \(T\) خط است که در خط \(i\)ام باید یک عدد صحیح و مثبت که برابر کمترین تعداد عملیات لازم برای برابر کردن همهی رشتهها در سناریوی \(i\)ام است را چاپ کنید.
مثالها
ورودی نمونه ۱
3
1 1
0
2 2
01
10
4 5
01010
00101
11000
00110
خروجی نمونه ۱
0
1
5
تست اول.
تنها یک رشته داریم، پس نیازی به انجام عملیات نیست. بنابراین پاسخ مسئله برابر ۰ خواهد بود.
تست دوم.
میتوانیم به ترتیب علمیاتهای زیر را انجام دهیم.
\[ \begin{array}{cc} 01 & \rightarrow & {\bf 10} \\ 10 & & 10 \\ \end{array} \]
بنابراین پاسخ مسئله برابر ۱ خواهد بود.
تست سوم.
میتوانیم به ترتیب عملیاتهای زیر را انجام میدهیم.
\[ \begin{array}{cccc} 01010 & & 01010 & & 01010 & & 01010 & & 01010 & & {\bf1}1010\\ 00101 & \rightarrow & {\bf11010} & \rightarrow & 11010 & \rightarrow & 11010 & \rightarrow & 11010 & \rightarrow & 11010\\ 11000 & & 11000 & & {\bf0011}0 & & {\bf110}10 & & 11010 & & 11010\\ 00110 & & 00110 & & 00110 & & 00110 & & {\bf110}10 & & 11010\\ \end{array} \]
بنابراین پاسخ مسئله برابر ۵ خواهد بود.