המונח ״ארכיטקטורת 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