در کشور متمدنی مانند امریکا رای گیری به صورت ایالتی برگزار می‌شود. به همین دلیل در صورتی که فردی مانند شوب بخواهد در انتخابات ریاست جمهوری انتخاب شود، برنامه‌ریزی تبلیغاتی خود را بر اساس ایالت‌ها بنا می‌گذارد. به این صورت که مکان‌های نشست‌های تبلیغاتی خود را تعیین می‌کند.

شوب برای رئیس‌جمهور شدن به یک برنامه‌ی تبلیغاتی احتیاج دارد که در آن معلوم باشد در هر ماه در کدام ایالت نشست انتخاباتی برگزار کند. از آن‌جایی که مردم هر ایالت سلایق سیاسی متفاوتی دارند، برایشان خیلی مهم است که فردی که برای نشست انتخاباتی برگزار کند. از آن‌جایی که مردم هر ایالت سلایق سیاسی متفاوتی دارند، برایشان خیلی مهم است که فردی که برای نشست تبلیغاتی به این شهر آمده به چه ترتیبی و در چه ایالت‌هایی نشست تبلیغاتی برگزار کرده. ولی به این دلیل که دغدغه‌های متفرقه برای افراد جامعه‌های متمدن زیاد است، حداکثر دو ماه گذشته را به خاطر می‌آورند.

رئیس دفتر آقای شوب بعد از زحمات فراوان توانست $m$ عدد لیست ۳ تایی $(a_i,b_i,c_i)$ در بیاورد به این معنا که چناچه آقای شوب در ایالت $c_i$ نشست برگزار کند در حالی که در ماه قبل در ایالت $b_i$ و دو ماه قبل در ایالت $a_i$ نشست برگزار کرده باشد، $w_i$ مقدار به نفع او خواهد بود. توجه کنید که ممکن است این لیست‌های ۳ تایی با هم اشتراک داشته باشند (برای مثال به ورودی توجه کنید). در ضمن اولین و دومین نشست تبلیغاتی اثری در رای‌ها نخواهد داشت.

فرض کنید آقای شوب می‌خواهد در دقیقا $n$ ماه نشست تبلیغاتی برگزار کند. $n$ و لیست‌های ۳ تایی به همراه $w_i$ ها داده شده‌اند. می‌خواهیم مقدار بیش‌ترین نفعی که می‌تواند این نشست‌ها داشته باشد را محاسبه کنیم.

در سطر اول فایل ورودی $m$ تعداد سه‌تایی‌ها و سپس $n$ آمده است. در $m$ سطر بعدی در سطر $i$ ام نخست $a_i$ و $b_i$ و $c_i$ و سپس با یک فاصله $w_i$ آمده است. $a_i$ و $b_i$ و $c_i$ ها حروف بزرگ انگلیسی بین $A$ تا $J$ هستند که شماره‌ی ایالت‌ها می‌باشند.

در یک سطر بیش‌ترین مقدار نفع انتخاباتی را بنویسید.

• سوال بعد
• سوال قبل