+ محدودیت زمان: ۱۰ ثانیه (برای تمامی زبان‌های برنامه‌نویسی) + محدودیت حافظه: ۵۱۲ مگابایت (برای تمامی زبان‌های برنامه‌نویسی) ---------- همانطور که همه می‌دانند، حسین نخبه هنرمند مورد علاقه‌ی ایرانیان است. از آن‌جا که ما حسین نخبه و آهنگ‌های او را دوست داریم، هرگز آن‌ها را به صورت رایگان دانلود نمی‌کنیم. باید آهنگ‌های حسین نخبه را از فروشگاه‌های مجاز خریداری کرد. اما اگر پول کافی برای خرید تمام آهنگ‌ها نباشد چه کار کنیم؟ برای ما $N$ آهنگ (شماره‌گذاری شده از $1$ تا $N$) و $M$ آلبوم (شماره‌گذاری شده از $1$ تا $M$) در دسترس وجود دارد. برای هر $i$ معتبر، آهنگ $i$-ام _ارزش موسیقیایی_ $v_i$ و $p_i$ تومان قیمت دارد و به آلبوم $a_i$ تعلق دارد. برای هر $i$ معتبر، آلبوم $i$-ام $b_i$ تومان قیمت دارد. اگر یک آلبوم را بخریم، همه‌ی آهنگ‌های این آلبوم به خریداری شده محسوب می‌شوند. هم‌چنین امکان خرید هر آهنگ به صورت جداگانه نیز وجود دارد. وظیفه شما ساده است. با توجه به بودجه $P$ (مقدار پولی که در اختیار داریم، به تومان)، بیشینه‌ی _ارزش موسیقیایی_ کل آهنگ‌هایی را که می‌توانیم بخریم را محاسبه کنید. ارزش موسیقیایی کل به عنوان مجموع ارزش‌های موسیقیایی تمام آهنگ‌های متمایزی که خریداری شده‌اند (به صورت جداگانه یا به عنوان بخشی از آلبوم‌ها) تعریف می‌شود. # ورودی + در اولین خط ورودی شامل سه عدد جدا از هم $N$، $M$ و $P$ است (در ابتدا $N$، بعد $M$ و سپس $P$ می‌آید). + $N$ خط بعدی دنبال می‌شود. برای هر $i$ ($1 \le i \le N$)، خط $i$-ام این خطوط شامل سه عدد جدا از هم $a_i$، $p_i$ و $v_i$ است. + خط آخر شامل $M$ عدد جدا از هم $b_1, b_2, \ldots, b_M$ است. # خروجی یک خط حاوی یک عدد چاپ کنید: بیشینه‌ی ارزش موسیقیایی کل آهنگ‌هایی که می‌توانیم بخریم. # محدودیت‌ها + $1 \le N, M, P \le 1,000$ + $1 \le b_i, p_i \le P$ برای هر $i$ معتبر + $1 \le v_i \le 10^6$ برای هر $i$ معتبر + $1 \le a_i \le M$ برای هر $i$ معتبر # مثال ## ورودی نمونه ۱ ``` 5 2 24 1 7 2 1 5 2 1 4 1 2 9 1 2 13 2 10 15 ``` ## خروجی نمونه ۱ ``` 7 ```