در کشور کرکسستان، $n$ کرکس زندگی می‌کنند. شرکت پرتقال که به تازگی گوشی‌های موبایل یوفون را تولید کرده، بعد از تحقیق بسیار زیاد بر روی کرکس‌ها، به این نتیجه رسیده که در کرکسستان، احساس حسادت شدیدی بین دوستان وجود دارد، به این شکل که اگر کرکس $i$ام یک گوشی یوفون خریداری کند، روی کرکس $j$ام به اندازه $f_{i,j}$ تاثیر خواهد گذاشت. (در صورت دوست نبودن دو کرکس، مقدار $f$ بین آن‌ها برابر با $0$ خواهد بود). دقت کنید که این حسادت یکطرفه است و لزومی ندارد کرکس $j$ ام نیز به همین اندازه بر روی کرکس $i$ام تاثیر بگذارد. همچنین مشخص شد که میزان علاقه کرکس $i$ام به خرید یوفون برابر $p_i$ است. یک کرکس در صورتی اقدام به خرید یوفون می‌کند که میزان علاقه او به‌یوفون به اضافه میزان حسادت او به افرادی که تا کنون یوفون را خریداری کرده‌اند، بیشتر یا مساوی قیمت یوفون باشد.

شرکت پرتقال قصد دارد در یک مناقصه $k$ روزه، بیشترین سود را از کرکسستان به دست بیاورد. مناقصه به این شکل انجام می‌شود که در ابتدای هر روز یک قیمت جدید برای گوشی‌های موبایل اعلام می‌شود. پس از آن هر کرکسی که تمایل به خرید یوفون داشته باشد، یک گوشی می‌خرد و به سرعت به همه دوستان خود یک پیامک با متن زیر می‌فرستد:

I have a YouPhone, On Your Face :P

بعد از اطلاع دوستان او از این خرید، ممکن است بعضی از آن‌ها نیز در همان روز با مراجعه به شرکت پرتقال، برای خود یوفون بخرند. به شرکت پرتقال کمک کنید تا با اعلام مناسب قیمت‌ها در $k$ روز، بیش‌ترین سود را به دست بیاورد.

• در سطر اول ورودی سه عدد $n$ و $m$ و $k$ آمده اند که به ترتیب تعداد کرکس‌ها، تعداد روابط دوستی بین آن‌ها و تعداد روزهای مناقصه را مشخص می‌کنند.
• در سطر دوم، $n$ عدد قرار دارند که مقدار $p_i$ ها را مشخص می‌کنند.
• در هر یک از $m$ سطر بعدی، سه عدد $x$ و $y$ و $f_{x, y}$ آمده‌اند که اندیس دو دوست و میزان تاثیرگذاری $x$ به $y$ را مشخص می‌کنند.
• $1 \leq n \leq 5000$
• $1 \leq k \leq 1000$
• $1 \leq m \leq 10^5$
• تمام اعداد ورودی بین ۱ و $10^5$ است
• در حداقل $70$ درصد تست ها مقدار $n$ و $k$ کمتر یا مساوی $200$ خواهد بود.

در تنها سطر خروجی، بیش‌ترین میزان سود برای شرکت پرتقال از فروش یوفون را چاپ کنید.

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

شرکت پرتقال می‌تواند در روز اول قمیت $100$ را اعلام کند. در این صورت ابتدا کرکس اول گوشی را می‌خرد و بعد از رسیدن پیامک او به کرکس دوم، او نیز گوشی را خریداری می‌کند. در روز دوم هم با اعلام قیمت $59$ برای گوشی‌ها، شرکت پرتقال می‌تواند یک گوشی به کرکس سوم بفروشد و در مجموع به سود $259$ برسد.