‎آمیرزا‎ که خیلی پیر شده است می‌خواهد وصیت‌نامه‌اش را تنظیم کرده و ارثیه‌اش را بین ‎$n$‎ وارثش تقسیم کند؛ اما از آن‌جا که می‌داند ورثه‌اش خیلی بی‌لیاقت‌اند، می‌خواهد با صرف کم‌ترین پول، همه‌شان را راضی کند‎.‎

از آن‌جا که آمیرزا خیلی مهربان است، برای جلب رضایت ورثه‌اش دست به هر کاری می‌زند‎!‎ در سوی دیگر، ورثه‌اش که از این موضوع باخبرند، به آمیرزا ‎$m$‎ گزاره می‌گویند که هر گزاره یکی از ‎$2$‎ نوع زیر را دارد. (در این گزاره‌ها منظور از ‎$h_i$‎ میزان پول (ارثیه)ای است که به وارث ‎$i$‎اُم می‌رسد و بالّطبع باید صحیح و مثبت باشد.) ‎

• گزاره مستقل : این گزاره‌ها به صورت ‎$h_i = c$‎ هستند. چنین گزاره‌ای معنی این را می‌دهد که وارث ‎$i$‎اُم دقیقاً $c$‎ واحد پول می‌خواهد. این گزاره‌ها در ورودی به صورتی نظیر $‎15 = 3$‎ آمده‌اند. این گزاره (برای مثال) مبیّن این خواسته‌است که پولی که به وارث ‎$15$‎اُم می‌رسد، باید دقیقاً ‎$3$‎ واحد باشد.
• گزاره حسادتی‎: فُرمَت این گزاره‌ها چنین است: ‎$h_i > h_j$‎. بدین معنی که پولی که به وارث ‎$i$‎اُم می‌رسد باید بیش‌تر از پولی باشد که به وارث ‎$j$‎اُم می‌رسد. ‎$9 > 7$‎ یک مثال از این گزاره‌ها در ورودی است و به معنی این است که وارث نهم باید پولی اکیداً بیش‌تر از پول وارث هفتم بگیرد.

دقت کنید که در یک گزاره‌ی حسادتی در ورودی، هر دو عدد، اندیس وراث هستند؛ حال آن‌که در گزاره‌ی مستقل، اوّلین عدد، اندیس بوده و عدد بعدی (سمت راستی)، مقدار است. اندیس‌ها در بازه‌ی ‎$[1‎, ‎n]$‎ هستند.

به آمیرزا کمک کنید و وصیت‌نامه‌ای برای او تنظیم کنید که اوّلاً تمام گزاره‌های گفته شده در آن برقرار باشد، ثانیاً مجموع پول‌های داده‌شده به وراث ‎($\sum_{i=1}^{n} h_i$)‎ در آن کمینه باشد.

• در سطر اول ورودی، عدد ‎$n$ (تعداد وارث‌ها) و پس از آن، عدد ‎$m$ (تعداد گزاره‌ها) قرار دارد.
• در ‎$m$‎ سطر بعدی، در هر سطر یکی از گزاره‌ها به فُرم گفته‌شده آمده است.
• می‌توانید مطمئن باشید که کارکتر میان دو عدد یک گزاره، حتماً یکی از ‎$2$‎ کاراکتر ‎$=$‎ یا ‎$>$‎ است که در دو طرف آن فاصله‌ی خالی ‎(space)‎ قرار گرفته‌است.
• هم‌چنین برای هر وارث حداکثر یک گزاره‌ی مستقل گفته خواهد شد و گزاره‌های حسادتی نیز دوبه‌دو متفاوتند.
• $1 \le n \leq 50,000$‎، ‎$1 \le m \le 200,000$‎ و سایر اعداد ورودی در بازه‌ی ‎$[1‎, ‎10^9]$‎ قرار دارند.

• در صورتی که آمیرزا در هیچ وصیت‌نامه‌ای نمی‌تواند همه‌ی ‎$m$‎ گزاره را ارضا کند، در یک خط عبارت ‎No Testament!‎ را بنویسید.
• در غیر این‌صورت در سطر اوّل خروجی، کم‌ترین میزان ‎»‎مجموع پول‌های داده‌شده‎«‎ به وراث در بهینه‌ترین وصیت‌نامه را بنویسید.
• سپس در سطر دوم خروجی، ‎$n$‎ عدد با یک فاصله از هم بنویسید که عدد ‎$i$‎اُم از سمت چپ ‎($1\le i \le n$)‎، پول اختصاص یافته به وارث ‎$i$‎اُم (یا همان ‎$h_i$‎) است.
• در صورتی که مسئله چند جواب داشته باشد، شما هرکدام را که دلتان خواست می‌توانید بنویسید.

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

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