به $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$ هستند و همواره از دو طرف بسته (مشمول)اند.
در خروجی یک عدد صحیح که کم‌ترین ناصافی قابل دسترسی (با اِعمال کردن عمل معکوس در محدوده بازه‌های داده شده، به تعداد متناهی بار)، است را بنویسید.