رشته‌های باینری


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

کشی nn رشته باینری به طول mm دارد. در هر عملیات می‌تواند یکی از این رشته‌ها را انتخاب کرده و پیشوندی از آن را برعکس کند. (کاراکترهای 0 را به 1 و 1 را به 0 تبدیل کنیم.)

توضیح تصویر

او می‌خواهد همه این رشته‌ها را باهم برابر کند. شما باید برای TT سناریوی مختلف، کمترین عملیات لازم برای رسیدن به این هدف را پیدا کنید.

ورودی🔗

در سطر اول ورودی عدد صحیح و مثبت TT آمده است که نشان دهنده‌ی تعداد سناریو هایی است که شما باید به آنها پاسخ دهید. 1T10001 \leq T \leq 1000

در سطر اول هر سناریو، دو عدد صحیح و مثبت nn و mm که با یک فاصله از هم جدا شده‌اند؛ آمده است. 1nm1000001 \leq n \cdot m \leq 100 \, 000 در nn سطر بعدی هر سناریو، در هر سطر یک رشته به طول mm آمده است.

تضمین می‌شود جمع تعداد کاراکترهای رشته‌ها از 100000100 \, 000 بیشتر نمی‌شود.

خروجی🔗

خروجی برنامه شامل TT خط است که در خط iiام باید یک عدد صحیح و مثبت که برابر کمترین تعداد عملیات لازم برای برابر کردن همه‌ی رشته‌ها در سناریوی iiام است را چاپ کنید.

مثال‌ها🔗

ورودی نمونه ۱🔗

3
1 1
0
2 2
01
10
4 5
01010
00101
11000
00110
Plain text

خروجی نمونه ۱🔗

0
1
5
Plain text

تست اول.

تنها یک رشته داریم، پس نیازی به انجام عملیات نیست. بنابراین پاسخ مسئله برابر ۰ خواهد بود.


تست دوم.

می‌توانیم به ترتیب علمیات‌های زیر را انجام دهیم.

01101010 \begin{array}{cc} 01 & \rightarrow & {\bf 10} \\ 10 & & 10 \\ \end{array}

بنابراین پاسخ مسئله برابر ۱ خواهد بود.


تست سوم.

می‌توانیم به ترتیب عملیات‌های زیر را انجام می‌دهیم.

010100101001010010100101011010001011101011010110101101011010110001100000110110101101011010001100011000110001101101011010 \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}

بنابراین پاسخ مسئله برابر ۵ خواهد بود.