خرید قانونی آهنگ


  • محدودیت زمان: ۱۰ ثانیه (برای تمامی زبان‌های برنامه‌نویسی)
  • محدودیت حافظه: ۵۱۲ مگابایت (برای تمامی زبان‌های برنامه‌نویسی)

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

برای ما NN آهنگ (شماره‌گذاری شده از 11 تا NN) و MM آلبوم (شماره‌گذاری شده از 11 تا MM) در دسترس وجود دارد. برای هر ii معتبر، آهنگ ii-ام ارزش موسیقیایی viv_i و pip_i تومان قیمت دارد و به آلبوم aia_i تعلق دارد. برای هر ii معتبر، آلبوم ii-ام bib_i تومان قیمت دارد. اگر یک آلبوم را بخریم، همه‌ی آهنگ‌های این آلبوم به خریداری شده محسوب می‌شوند. هم‌چنین امکان خرید هر آهنگ به صورت جداگانه نیز وجود دارد.

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

ورودی🔗

  • در اولین خط ورودی شامل سه عدد جدا از هم NN، MM و PP است (در ابتدا NN، بعد MM و سپس PP می‌آید).
  • NN خط بعدی دنبال می‌شود. برای هر ii (1iN1 \le i \le N)، خط ii-ام این خطوط شامل سه عدد جدا از هم aia_i، pip_i و viv_i است.
  • خط آخر شامل MM عدد جدا از هم b1,b2,,bMb_1, b_2, \ldots, b_M است.

خروجی🔗

یک خط حاوی یک عدد چاپ کنید: بیشینه‌ی ارزش موسیقیایی کل آهنگ‌هایی که می‌توانیم بخریم.

محدودیت‌ها🔗

  • 1N,M,P1,0001 \le N, M, P \le 1,000
  • 1bi,piP1 \le b_i, p_i \le P برای هر ii معتبر
  • 1vi1061 \le v_i \le 10^6 برای هر ii معتبر
  • 1aiM1 \le a_i \le M برای هر ii معتبر

مثال🔗

ورودی نمونه ۱🔗

5 2 24
1 7 2
1 5 2
1 4 1
2 9 1
2 13 2
10 15
Plain text

خروجی نمونه ۱🔗

7
Plain text
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.