{"trustable":true,"sections":[{"title":"وصف المسألة","value":{"format":"MD","content":"**المسألة الأصلية من: NOI 2001**\n\nقرر جنرالات القيادة نشر قوات المدفعية الخاصة بهم على خريطة الشبكة $N\\times M$ . تتكون الخريطة $N\\times M$ من $N$ صف و $M$ أعمدة، حيث يمكن أن تكون كل خانة في الخريطة سواء جبلية (ممثلة بالحرف `H`) أو سهلة (ممثلة بالحرف `P`)، كما هو موضح في الصورة أدناه. يمكن نشر قوة المدفعية على كل خانة سهلة بحيث لا تزيد قوات المدفعية عن واحدة في كل خانة (لا يمكن نشر قوات المدفعية على الجبال)؛ ويظهر نطاق هجوم قوة المدفعية على الخريطة كما هو موضح في اللون الأسود:\n\n![cannon.jpeg](CDN_BASE_URL/4bf6168d2234dc699daa2ffe53d7c078?v\u003d1701483990)\n\nإذا تم نشر قوة المدفعية على الخانة السهلة المظللة في الصورة، فإن الشبكة السوداء تمثل المنطقة التي يمكنها الهجوم عليها: اثنين في الاتجاه الأفقي واثنين في الاتجاه الرأسي. كما هو واضح من الصورة، فإن نطاق هجوم قوة المدفعية لا يتأثر بنوع التضاريس. \nالآن، يخطط الجنرالات لنشر قوات المدفعية، مع الحرص على تجنب الأضرار الجانبية (ضمان عدم تبادل الهجوم بين أي اثنين من قوات المدفعية، أي أن أي قوة مدفعية لا تكون في نطاق هجوم أي قوة مدفعية أخرى)، وذلك بحيث يمكن نشر أكبر عدد ممكن من قوات المدفعية في منطقة الخريطة بأكملها."}},{"title":"تنسيق الإدخال","value":{"format":"MD","content":"السطر الأول يحتوي على رقمين صحيحين مفصولين بمسافة، يمثلان $N$ و $M$ بالترتيب؛ \nالسطور التالية $N$، كل سطر يحتوي على $M$ حرفًا متتالية (`P` أو `H`)، دون وجود مسافات بينها. تمثل كل سطر بالترتيب بيانات كل صف في الخريطة."}},{"title":"تنسيق الإخراج","value":{"format":"MD","content":"سطر واحد فقط، يحتوي على عدد صحيح $K$، يمثل الحد الأقصى لعدد قوات المدفعية التي يمكن نشرها."}},{"title":"مثال","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 4\nPHPP\nPPHH\nPPPP\nPHPP\nPHHP\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"نطاق البيانات والتلميحات","value":{"format":"MD","content":"$N \\le 100, M \\le 10$."}}]}