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

---

تعدادی پردازش و تعدادی پردازش‌گر داریم (پردازش‌ها با شماره‌های \(1\) تا \(k\) و پردازش‌گرها با شماره‌های \(1\) تا \(n\) شماره گذاری شده‌اند). پردازش \(i\) به \(d_i\) ثانیه زمان نیاز دارد تا انجام شود و یک مجموعه از پردازش‌های پیش‌نیاز دارد. می‌خواهیم برای انجام هر پردازش یک زمان برای انجام شدن و یکی از پردازش‌گرها انتخاب کنیم تا در آن زمان آن پردازش را به آن پردازش‌گر مشخص شده اختصاص بدهیم. اگر یکی از پیش‌نیازهای یک پردازش پیش از اختصاص آن به پردازش‌گرش انجام نشده باشند، به اندازه‌ی مشخصی (وابسته به پردازش و پیش‌نیاز) به زمان انجام آن پردازش اضافه می‌شود (نیاز به مقداری محاسبات اضافی دارد).

می‌خواهیم طوری پردازش‌ها را در زمان بین پردازش‌گرها پخش کنیم که مجموع زمان پایان‌های پردازش‌ها کمینه شود. هر پردازش باید در یک بازه پشت‌سرهم از زمان در یکی از پردازش‌گرها انجام شود و هر یک از پردازش‌گرها در هر لحظه حداکثر یک پردازش را انجام می‌دهند.

ورودی

در خط اول ورودی دو عدد \( n \) و \( k \) آمده است که تعداد پردازش‌گرها و پردازش‌ها را نشان می‌دهند.

در خط بعدی \( k \) عدد آمده که \( i \)امین عدد نشان دهنده‌ی زمانی که برای انجام پردازش \( i \) نیاز است.

در خط بعدی یک عدد \( m \) آمده است که نشان دهنده‌ی تعداد روابط پیش‌نیازی بین پردازش‌هاست.

در \( m \) خط بعدی در هر خط سه عدد \(v\) و \(u\) و \(c\) آمده است که نشان می‌دهد پردازش \(v\) پیش‌نیاز پردازش \(u\) است و در صورت رعایت نشدن این پیش‌نیازی پردازش \(u\)، \(c\) ثانیه بیشتر طول می‌کشد.

\[1 \le n, k \le 100\] \[1 \le m \le 10\ 000\] \[1 \le c, d_i \le 1\ 000\ 000\]

خروجی

خروجی باید شامل \( k \) خط باشد که در خط \(i\)ام از آن دو عدد \(w\) و \(t\) آمده است که نشان می‌دهند پردازش \(i\)ام در لحظه‌ی \(t\) به پردازش‌گر \(w\) اختصاص داده می‌شود.

هرچه مجموع زمان پایان پردازش‌ها کمتر باشد کد شما نمره‌ی بهتری دریافت می‌کند. در صورت غیرقابل انجام بودن خروجی نمره‌ای دریافت نمی‌کنید (اختصاص دادن یک پردازش به پردازش‌گری که در حال پردازش کردن است).

مثال

ورودی نمونه

1 3
1 1 1
3
1 2 1
2 3 2
3 1 3

خروجی نمونه

1 3
1 0
1 2

برای ورودی نمونه خروجی داده شده بهترین خروجی است (مجموع زمان پایان‌ها \(4 + 2 + 3 = 9\) ) ولی برای مثال خروجی‌های زیر نیز قابل قبول است.

1 0
1 4
1 5

• مجموع زمان پایان‌ها \(4 + 5 + 6 = 15\)

1 4
1 3
1 0

• مجموع زمان پایان‌ها \(5 + 4 + 3 = 12\)