يُطلق مصطلح «معمارية Harvard» على حاسوب ذي ذاكرتين منفصلتين مادياً للتعليمات والبيانات. نشأ المصطلح مع حاسوب Harvard Mark I، الذي سلّمته IBM عام 1944، وكان يستخدم شريطاً ورقياً للتعليمات ومرحلات للبيانات.

تستخدم بعض المتحكمات الدقيقة الحديثة معمارية Harvard، لكن ليس الشريط الورقي والمرحلات! تُنظّم ذاكرة البيانات في بنوك، يحتوي كل منها على العدد نفسه من عناصر البيانات. لكل تعليمة تشير إلى البيانات إزاحة بالبايت $f$ داخل بنك، وبت $a$ يُستخدم لاختيار البنك المشار إليه. إذا كان $a$ يساوي $0$، فيُشار إلى البنك $0$. وإذا كان $a$ يساوي $1$، فإن القيمة في مسجل اختيار البنك (BSR) تحدد البنك المستخدم. افترض أن كل تعليمة تستغرق الوقت نفسه للتنفيذ، وأن هناك تعليمة يمكنها ضبط قيمة BSR.

الصورة من Wikimedia Commons

مثلاً، افترض وجود 4 بنوك، حجم كل منها 8 بايتات. للوصول إلى الموقع $5$، يمكن استخدام تعليمة واحدة مع $a = 0$ و$f = 5$، أو ضبط BSR على $0$ بتعليمة ثم استخدام تعليمة مع $a = 1$ و$f = 5$. الطريقة الأولى أسرع لأنها لا تتطلب ضبط BSR.

افترض الآن، مع الذاكرة نفسها، أن الموقع المطلوب الوصول إليه هو $20$. لا تنجح هنا إلا طريقة واحدة: تنفيذ تعليمة تضبط BSR على $2$ (إلا إذا كانت قيمته بالفعل $2$)، ثم استخدام تعليمة مع $a = 1$ و$f = 4$.

البرنامج هو تسلسل من العمليات. وكل عملية هي إما

• إشارة إلى متغير، تُكتب Vi، حيث $i$ عدد صحيح موجب، أو

• تكرار، يُكتب Rn <program> E، حيث $n$ عدد صحيح موجب و<program> برنامج اعتباطي. تكافئ هذه العملية $n$ نسخ متتالية من <program>.

مهمتك هي تحديد أقل زمن تشغيل للبرامج. وتحديداً، عند إعطائك عدد بنوك الذاكرة وحجمها وبرنامجاً لتنفيذه، أوجد أقل عدد من التعليمات (التي تشير إلى مواقع الذاكرة وقد تضبط BSR) يجب تنفيذها لتشغيل البرنامج. لهذا عليك إيجاد توزيع للمتغيرات على بنوك الذاكرة يحقق أقل زمن تنفيذ، ثم الإبلاغ عن هذا الزمن، أي عدد الإشارات إلى الذاكرة وعمليات ضبط مسجل BSR المطلوبة. قيمة BSR غير معرّفة في البداية، ولا تتغير إلا عندما تضبطها تعليمة صراحةً.

الإدخال

يتكون الإدخال من حالة اختبار واحدة تتألف من سطرين. يحتوي السطر الأول على عددين صحيحين $b$ و$s$، حيث $1 \le b \le 13$ هو عدد بنوك الذاكرة و$1 \le s \le 13$ هو عدد المتغيرات التي يمكن تخزينها في كل بنك. يحتوي السطر الثاني على برنامج غير فارغ يتألف من 1 000 عنصر على الأكثر تفصل بينها مسافات (يُعد كل من Rn وVi وE عنصراً واحداً).

يمكنك افتراض ما يأتي:

• في التكرار Rn، يحقق عدد التكرارات $1 \le n \le 10^6$.

• في عملية الحلقة Rn <program> E، يكون جسم الحلقة <program> غير فارغ.

• في الإشارة إلى متغير Vi، يحقق فهرس المتغير $1 \le i \le \min(b \cdot s, 13)$.

• إجمالي عدد الإشارات إلى المتغيرات أثناء تنفيذ البرنامج لا يزيد على $10^{12}$.

الإخراج

اعرض أقل عدد من التعليمات التي يجب تنفيذها لإكمال البرنامج.

أمثلة

الإدخال 1

1 2
V1 V2 V1 V1 V2

الإخراج 1

5

الإدخال 2

2 1
V1 V2 V1 V1 V2

الإخراج 2

6

الإدخال 3

1 2
R10 V1 V2 V1 E

الإخراج 3

30

الإدخال 4

4 1
V1 R2 V2 V4 R2 V1 E V3 E

الإخراج 4

17