فرهاد جدولی ۱۴۰۱ × ۳۰۰ دارد که در ابتدا، تمام خانه‌های آن سفید هستند. او قصد دارد تعدادی از خانه‌های جدول را سیاه کند طوری که هر خانه‌ی سفید در جدول نهایی، مجاور رأسی حداقل یک خانه‌ی سیاه باشد. دو خانه‌ی متمایز، مجاور رأسی هستند اگر مرزهایشان حداقل در یک نقطه با هم اشتراک داشته باشند. مثلا در جدول زیر، خانه‌های B و C مجاور رأسی خانه‌ی A هستند ولی خانه‌ی D مجاور رأسی خانه‌ی A نیست.

فرهاد برای رسیدن به هدف خود می‌تواند در هر روز، یک زیرجدول دلخواه را انتخاب نماید و با استخدامِ یک نقاشِ روزمزد، تمامی خانه‌های آن زیرجدول را سیاه کند. منظور از یک زیرجدول، مجموعه‌ای خانه‌هایی است که از تلاقی تعدادی سطر متوالی و تعدادی ستون متوالی در جدول اصلی حاصل می‌شود. به عنوان مثال، جدول بالا دارای ۴ زیرجدول با ابعاد ۲ × ۳ (حاصل تلاقی ۲ سطر متوالی و ۳ ستون متوالی) است. اگر ابعاد زیرجدول انتخابی فرهاد در یک روز، $h \times w$ باشد، او باید $h \times w$ سکه (به تعداد خانه‌های زیرجدول) برای خرید رنگ بپردازد و علاوه بر آن، لازم است ۲ سکه نیز به عنوان هزینه‌ی استخدام نقاش در آن روز پرداخت نماید. مثلا اگر در یک روز، او یک زیرجدول ۲ × ۲ را انتخاب کند، در مجموع باید به اندازه‌ی $۲ + ۲ \times ۲ = ۶$ سکه در آن روز هزینه کند. لازم به ذکر است که حتی اگر برخی از خانه‌های زیرجدول انتخابی فرهاد در یک روز، از قبل سیاه باشند، تغییری در هزینه‌ی آن روز فرهاد ایجاد نمی‌شود.

• الف) ثابت کنید فرهاد می‌تواند با پرداخت ۱۴۰۱۰۰ سکه، به هدف خود برسد. (۲۰ امتیاز)

• ب) ثابت کنید فرهاد نمی‌تواند با هزینه‌ای کمتر از ۱۴۰۱۰۰ سکه، به هدف خود برسد. (۲۰ امتیاز)