+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- بعد از این که محمدرضا هرطور شده رفتش دانشگاه شریف حالا به دلایل عجیبی مدرسه‌های شهرش بهش پیشنهاد دادن که بیاد اونجا درس بده. محمدرضا که تحت هیچ شرایطی دیگه نمیخواد از دانشگاه اخراج بشه باید سر همه‌ی کلاسای دانشگاه شرکت کنه. محمدرضا در طول هفته $n$ کلاس در دانشگاه داره. کلاس‌های دانشگاه میتونه هر ساعتی در روز و هر روزی در هفته باشه. در کل $m$ مدرسه به محمدرضا پیشنهاد تدریس داده‌اند. کلاس‌های تدریس هم توی شهر محمدرضا روز و ساعت خاصی نداره و می‌تونه هر موقعی باشه. هر کلاس هم درامد خاص خودش را دارد. محمدرضا چون خیلی پول‌پرسته و به روح معلمی هیچ اهمیتی نمیده میخواد بیشترین سود ممکن در هفته رو داشته باشه. ولی خب خودش نمیدونه چجوری باید کلاساشو انتخاب کنه و شما باید به اون کمک کنید. به این امید که شاید درصدی از درامدشو بهتون بده. به دلیل متروهای فوق سریع از دانشگاه به شهر محمدرضا، اون میتونه در زمان بسیار کمی خودشو به شهرشون برسونه و بره سر کلاس. یعنی اگر دوشنبه‌ها تا ساعت ۱۷ داخل دانشگاه کلاس داره میتونه توی شهرشون از ساعت ۱۷ تا ۱۹ درس بده و به موقع برسه. # ورودی در خط اول ورودی دو عدد $n$ و $m$ آمده است که به ترتیب نمایانگر تعداد کلاس های دانشگاه و تعداد مدرسه‌های پیشنهاد شده به محمدرضا است. در $n$ خط بعدی در هر خط سه عدد $d$، $s$ و $e$ می‌آید که به ترتیب نشان‌دهنده‌ی روز برگزاری کلاس(۰ به معنی شنبه، ۱ به معنی یکشنبه ...)، ساعت شروع و ساعت پایان کلاس است. در $m$ خط بعدی در هر خط چهار عدد $d$، $s$ ،$e$ و $w$ می‌آید که به ترتیب نشان‌دهنده‌ی روز برگزاری کلاس(۱ به معنی شنبه، ۲ به معنی یکشنبه ...)، ساعت شروع، ساعت پایان و درآمد حاصل از کلاس است. $$ 1 \le n,m \le 16 $$ $$ 0 \le s < e \le 24 $$ $$ 0 \le d < 7 $$ $$ 1 \le w \le 10\ 000 $$ # خروجی در تنها خط خروجی بیشترین درآمد ممکن برای محمدرضا را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 2 2 1 13 15 3 13 15 1 15 17 5000 3 12 14 2000 ``` ## خروجی نمونه ۱ ``` 5000 ``` ## ورودی نمونه ۲ ``` 2 3 1 8 10 1 10 12 2 19 22 10000 2 18 20 7000 2 21 24 5000 ``` ## خروجی نمونه ۲ ``` 12000 ```