+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ***** شرکت گذشته‌سازان فعلی به یک مشکل جدی برنامه‌نویسی خورده است و قصد استخدام یک برنامه‌نویس را دارد؛ از این رو آن‌ها مشکلشان را به عنوان یک سوال در اینجا گذاشتند تا افرادی که واقعا قادر به حل مشکلشان هستند را بیابند: این شرکت $n$ کار دارد (آن‌ها را با اعداد ۱ تا $n$ شماره‌گذاری می‌کنیم) که انجام دادن کار $i$ام، $t_i$ روز طول خواهد کشید. شما باید برنامه‌ای بنویسید که برنامه‌ای برای انجام دادن این کار‌ها چاپ کند که کمترین ضرر را داشته باشد. فقط قبل از این که دست به کد شوید به نکات زیر توجه کنید: ۱- هر روز را می‌توان به انجام دادن فقط یک کار اختصاص داد. ۲- تا زمانی که کار نیمه‌کاره‌ای وجود دارد نمی‌توان کار دیگری را شروع کرد. در نتیجه در هر لحظه حداکثر یک کار نیمه‌کاره وجود دارد؛ به عبارت دیگر، زمانی که یک کار را شروع می‌کنیم، تا زمان پایان یافتن آن نباید کار دیگری شروع شود. ۳- تعدادی از کار‌ها هستند که پیش‌نیاز یک سری دیگر از کار‌ها هستند؛ یعنی تا زمانی که پیش‌نیاز یک کاری به طور کامل انجام نشود، نمی‌توان سراغ خود آن کار رفت. ۴- بعضی از کارها نسبت به هم «فوری» هستند؛ یعنی هر چقدر فاصله‌ی تمام شدنشان از هم کمتر باشد، بهتر است. در نتیجه به اندازه‌ی فاصله‌ی تمام شدن این دو کار ما ضرر خواهیم کرد. ۵- بعضی از کارها نسبت به هم «نافوری» هستند؛ یعنی بهتر است که حداقل ۱۵ روز بین تمام شدن این کار‌ها فاصله باشد. در نتیجه اگر فاصله‌ی تمام شدن این دو کار را $d$ در نظر بگیریم، به اندازه‌ی $max(0, 15 - d) $ ضرر خواهیم کرد. **در این سوال، بسته به تعداد تست‌هایی که درست پاسخ دهید نمره می‌گیرید. برنامه‌ی شما هرچه بهینه‌تر باشد، نمره‌ی بیشتری دریافت خواهید کرد.** # ورودی در سطر اول ورودی چهار عدد $n$، $m$، $f$ و $h$ آمده‌است که به ترتیب نمایانگر تعداد کار‌ها، تعداد جفت کار‌هایی که اولی پیش‌نیاز دومی است، تعداد جفت‌ کار‌هایی که نسبت به هم «فوری» هستند و تعداد جفت کار‌هایی که نسبت به هم «نافوری» هستند می‌باشد. سپس در سطر بعدی $n$ عدد آمده است که عدد $i$ام نمایانگر $t_i$ می‌باشد. بعد از آن، در $m$ سطر بعدی، در هر سطر، به ترتیب دو عدد $a$ و $b$ آمده است که نمایانگر این است که کار شماره‌ی $a$ باید قبل از کار شماره‌ی $b$ انجام شود. سپس در $f$ سطر بعدی، در هر سطر، دو عدد $a$ و $b$ آمده است که نمایانگر این است که کار شماره‌ی $a$ و $b$ نسبت به هم «فوری» هستند. و در نهایت در $h$ سطر بعدی، در هر سطر، دو عدد $a$ و $b$ آمده است که نمایانگر این است که کار شماره‌ی $a$ و $b$ نسبت به هم «نافوری» هستند. $$ 1 \le n, m, f, h, t_i \le 15 $$ # خروجی در تنها سطر خروجی کمترین مقدار ضرر را چاپ کنید. اگر راهی برای انجام دادن کار‌ها با توجه به شرایط پیش‌نیازی وجود ندارد در یک خط عبارت "varshekast shodin" را چاپ نمایید. # مثال ## ورودی نمونه ۱ ``` 3 2 1 1 1 2 3 1 2 2 3 1 2 2 3 ``` ## خروجی نمونه ۱ ``` 14 ``` در نمونه‌ی بالا،‌ با توجه به شرایط پیش‌نیازی می‌توان فهمید که تنها حالتی که شرایط پیش‌نیازی در آن رعایت شود حالت ۱،۲،۳ است که مقدار ضرر این حالت با توجه به نکات زیر حساب می‌شود: کار‌های ۱ و ۲ فوری هستند و فاصله‌ی بین پایان این دو کار ۲ روز می‌باشد؛ پس دو واحد ضرر ایجاد شده است. کار‌های ۲ و ۳ نافوری هستند و فاصله‌ی بین پایان این دو کار ۳ روز می‌باشد؛ پس به اندازه‌ی ۳ - ۱۵ واحد ضرر ایجاد می‌کنند که با ۲ واحد ضرر قبلی می‌شود ۱۴ واحد ضرر.

حل سؤال در بانک سؤالات