+ محدودیت زمان: ۲ ثانیه
+ محدودیت حافظه: ۵۱۲ مگابایت
----------
در بندر یک ساحل، $n$ مدرسه وجود دارد. همه قایق های یک مدرسه یکسان و غیرقابل تشخیص‌اند اما قایق های مدرسه های مختلف رنگ های مختلفی دارند و از یکدیگر قابل تشخیص‌اند.
در فستیوال تابستانی، هر مدرسه مانند مدرسه $i$ام تصمیم میگیرد یا قایقی نفرستد، یا هر تعداد قایق بین $a_i$ و $b_i$ بفرستد. ($a_i \leq b_i$)
همچنین اگر مدرسه $i$ام تصمیم بگیرد قایق بفرستد، تعداد قایق های فرستاده شده توسط مدرسه $i$ باید از تعداد قایق های فرستاده شده توسط مدارس با شماره های کمتر از $i$، اکیدا بزرگتر باشد.
تعداد حالت‌های فرستادن قایق توسط این $n$ مدرسه را بدست آورید در صورتی که حداقل یک مدرسه قایق بفرستد.
# ورودی
در خط اول $n$، تعداد مدرسه ها، به شما داده میشود.
در $i$امین خط بعدی از $n$ خط، $a_i$ و $b_i$ داده میشود.
$$1\leq n \leq 500$$
$$1\leq a_i \leq b_i \leq 10^9$$
# خروجی
در تنها خط خروجی تعداد حالت های فرستادن قایق را چاپ کنید. چون این عدد ممکن است بزرگ باشد کافی است باقی مانده تقسیم آن بر $10^9+7$ را چاپ کنید.
# زیرمسئله‌ها
| زیرمسئله | نمره | محدودیت |
|:---------------------:|:----------------:|:-------------------:|
| ۱ | ۹ | $$a_i=b_i$$|
| ۲ | ۲۲ | $$\sum b_i-a_i \leq 10^6$$|
| ۳ | ۲۷ | $$n\leq100$$ |
| ۴ | ۴۲ | بدون محدودیت اضافی |
# مثال
## ورودی نمونه ۱
```
2
1 2
2 3
```
## خروجی نمونه ۱
```
7
```
۴ راه وجود دارد که تنها یک مدرسه قایق بفرستد. ۳ راه هم وجود دارد که هر دو مدرسه قایق بفرستند.
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۵۱۲ مگابایت
----------
تیزی و کسری روی یک گراف همبند بازی میکنند. هر کدام از آنها روی یکی از راس های گراف قرار گرفته‌اند.
دو راس از این گراف راس های سرور نام دارند که این دو راس حتما با یک یال بهم وصلند.
تیزی و کسری یکی درمیان حرکت میکنند و ابتدا تیزی حرکت میکند. آنها در هر ثانیه میتوانند به یکی از راس های مجاور راس فعلی خود بروند اما مجبور به حرکت نیستند. قطع کردن سیم های یک سرور هم یک ثانیه طول میکشد.
هدف تیزی این است که به یک راس سرور برسد و سیم آن را قطع کند. کسری میخواهد جلوی او را بگیرد. کسری در صورتی برنده میشود که تا ابد جلوی کشیدن سیم سرور توسط تیزی را بگیرد. یا اینکه قبل از کشیده شدن سیم سرور با تیزی در یک راس باشد.
اما کسری خوابش می‌آید و میخواهد بیشتر بخوابد.
او میخواهد آنقدر بخوابد تا بعد از بیدار شدن همچنان مطمئن باشد میتواند از تیزی ببرد. بیشترین تعداد ثانیه‌ای که کسری میتواند به جای بازی کردن بخوابد را پیدا کنید.
دقت کنید که کسری در زمانی که خواب است حتی اگر با تیزی در یک راس قرار بگیرد برنده نمیشود.
# ورودی
در خط اول ورودی $n$ و $m$ به شما داده میشود که به ترتیب تعداد راس های گراف و تعداد یال های آن است.
در خط بعدی ۴ عدد $k$ و $t$ و $a$ و $b$ به شما داده میشود که $t$ شماره راس ابتدایی تیزی است و $k$ شماره راس ابتدایی کسری. $a$ و $b$ شماره راس های دو سرور هستند.
در هر یک از $m$ خط بعدی دو عدد $v$ و $u$ به شما داده میشود که نشان دهنده ی یک یال بین $v$ و $u$ است.
$$4 \leq n \leq 200\ 000$$
$$3 \leq m \leq 600\ 000$$
$$1\leq t,k,a,b,v,u \leq n$$
# خروجی
در تنها خط خروجی حداکثر زمانی که کسری میتواند بخوابد تا باز هم تیزی را ببرد بدهید. اگر کسری نمیتواند تیزی را ببرد $-1$ چاپ کنید.
# زیر مسئله‌ها
| زیرمسئله | نمره | محدودیت |
|:---------------------:|:----------------:|:-------------------:|
| ۱ | ۳۰ | $$n \le 800, m\le 1 \ 600$$|
| ۲ | ۷۰ | بدون محدودیت اضافی|
# مثال
## ورودی نمونه ۱
```
6 6
1 2 3 4
1 5
5 6
6 3
6 4
1 2
3 4
```
## خروجی نمونه ۱
```
1
```
## ورودی نمونه ۲
```
6 7
5 6 1 2
6 3
1 2
1 3
2 3
1 5
2 4
5 4
```
## خروجی نمونه ۲
```
0
```
+ محدودیت زمان: ۲.۵ ثانیه
+ محدودیت حافظه: ۱۶۰ مگابایت
----------
یک گراف $n$ راسی همبند با $m$ یال وزن‌دار داریم. در راس $i$ ام $p_i$ نفر زندگی میکنند.
وزن های این $m$ یال متفاوت است.
تیزی $k$ یال دیگر بجز این $m$ یال دارد که وزن های آنها هنوز تعیین نشده است. او میتواند وزن این یال ها را هر عددی بگذارد. (حتی برابر با وزن یکی از $m$ یال ابتدایی)
تیزی پس از تعیین وزن یال های جدیدش، باید یک MST از گراف انتخاب کند. اگر چند حالت برای انتخاب این MST وجود دارد او میتواند هرکدام از حالت ها را بردارد.
سپس هر نفر در هر یک از راس ها به سمت راس ۱ حرکت میکند. هر نفر برای عبور از یک یال باید به اندازه وزن آن یال به تیزی پول بدهد.
طبعن افراد فقط میتوانند از یال های MST انتخاب شده ی تیزی استفاده کنند!
تیزی میخواهد ماکسیمم پول را کسب کند. به او بگویید این مقدار چقدر است اگر او وزن $k$ یال را به بهترین حالت تعیین کند.
# ورودی
در خط اول ورودی $n$ و $m$ و $k$ به شما داده میشود که به ترتیب تعداد راس های گراف و تعداد یال های ابتدایی و تعداد یال هایی است که تیزی وزن آنها را تعیین خواهد کرد.
در هر یک از $m$ خط بعدی ۳ عدد $a$ و $b$ و $c$ به شما داده میشود که نشان دهنده وجود یالی بین $a$ و $b$ با وزن $c$ است. تضمین میشود همه $c$ ها متفاوتند.
در هر یک از $k$ خط بعدی ۲ عدد $a$ و $b$ به شما داده میشود که نشان‌دهنده یک یال بین $a$ و $b$ است که وزن این یال را تیزی تعیین خواهد کرد.
در خط آخر $n$ عدد $p_1,p_2,...,p_n$ به شما داده میشود.
$$1\leq n \leq 10^5$$
$$1\leq m \leq 3*10^5$$
$$1\leq k \leq 20$$
$$1\leq p_i,c \leq 10^6$$
# خروجی
در تنها خط خروجی ماکسیمم پولی که تیزی میتواند کسب کند را بدهید.
# مثال
## ورودی نمونه ۱
```
5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50
```
## خروجی نمونه ۱
```
400
```
تیزی میتواند وزن یال بین ۱ و ۳ را ۵ قرار دهد و ۴۰۰ تا سود کند.