به $n$ تا بیت صفر یک یک که پشت سر هم از چپ به راست چسبیده باشند، یک دنباله‌ی باینری به‌طول $n$ می‌گوییم. برای هر دنباله‌ی باینری یک میزان «ناصافی» تعریف می‌کنم که عبارت است از تعداد دفعاتی که با خواندن بیت به بیت از چپ به راست دنباله، بیت عوض می‌شود. برای مثال ناصافی دنباله‌ی 00111 برابر یک، ناصافی دنباله‌ی 10101 برابر چهار و ناصافی دنباله‌ی 0000 برابر با صفر است. پویا علاقه زیادی به صاف کردن دنباله‌های ناصاف دارد! یک روز صبح، پدر پویا به پویا یک دنباله به‌طول $n$ و $k$ بازه‌ی ناتهی در محدوده‌ی $1$ تا $n$ می‌دهد و از پویا می‌خواهد با تعدادی «تغییرِ بازه‌ای» میزان ناصافی دنباله را حداقل کند. هر تغییر بازه‌ای، انتخاب یکی از بازه‌های داده شده توسط پدر پویا و معکوس (تبدیل صفر به یک و بالعکس) کردن تمام بیت‌های درون آن بازه است. برای مثال فرض کنید دنباله اولیه 00110100 باشد (بیت‌های شماره ۳ و ۴ و ۷ این دنباله یک است). علاوه بر این، فرض کنید بازه‌هایی که پدر پویا در کنار این دنباله به پویا داده هم بازه‌های $[2,5]$ و $[1,7]$ و $[6,7]$ باشد، پویا می‌تواند با انتخاب دو بازه‌ی آخر (هر کدام یک بار) دنباله را به 11001100 تبدیل کند که ناصافی را از میزان ۴ اولیه به مقدار ۳ می‌رساند که میزان کمینه ناصافی قابل رسیدن از رشته اولیه با کمک بازه‌های داده شده است. می‌دانیم که بازه‌های داده شده به صورت $[X,Y]$ که $1 \leq X \leq Y \leq n$ هستند و همواره از دو طرف بسته (مشمول)اند.

• سطر اوّل ورودی شامل دو عدد n (طول دنباله)‌ و سپس k (تعداد بازه‌ها) است.
• در سطر بعدی دنباله‌ای به‌طول n از صفر و یک وجود دارد.
• سپس در k سطر بعدی در هر سطر ابتدا و انتهای یکی از بازه‌های داده شده توسط پدر پویا ذکر می‌شود.
• $1 \leq n, k \leq 10000$
• در ۳۰ درصد از ورودی‌ها، تضمین می‌شود که $1 \leq n, k \leq 300$
• در ۵۰ درصد از ورودی‌ها به‌ازای هر دو بازه‌ی $[x_1,y_1]$ و $[x_2,y_2]$ که داشته باشیم $x_1\leq x_2$، آنگاه الزاماً یا داریم $y_1<x_2$ و یا داریم $y_2\leq y_1$.

در خروجی یک عدد صحیح که کم‌ترین ناصافی قابل دسترسی (با اِعمال کردن عمل معکوس در محدوده بازه‌های داده شده، به تعداد متناهی بار)، است را بنویسید.

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

• سوال بعد
• سوال قبل