Занурення за скарбами#3783
Легенди часто розповідають про великі скарби. Але рідко випадає нагода справді натрапити на ті скарби. Більшість із них загублені в морі або сховані під горами. Але, як ти дізнався від одного зі своїх найбільших кумирів, скарби мають бути у музеї. І зараз у тебе є шанс це здійснити.
Під час експедиції ти знайшов велику мережу печер. Місцевий шаман казав про неймовірні цінності, які його предки сховали у цих печерах. Він навіть дав тобі стародавню карту, на якій зображена мережа печер і місця розташування скарбів. На жаль, ця мережа повністю затоплена. Оскільки подорож сюди займає купу часу, ти вирішив зробити коротке занурення й розвідати печери. Але коли повернувся до входу в мережу печер, отримав новину... поруч щойно вивергнувся вулкан. Ледве не гарантовано, що лава накриє входи в печери, і скарби будуть втрачені назавжди.
Тепер усе залежить від тебе. У тебе залишилося мало часу і лише один жалюгідний балон з повітрям. Отже, є всього одне занурення. Але як вибрати маршрут? Мережа печер величезна, і варто врятувати якомога більше скарбів. Ти згадав свої студентські роки на факультеті комп'ютерних наук... І тут тебе осяяло. У тебе ж із собою ноутбук. Можна написати програму, яка допоможе визначити найкращий спосіб врятувати скарби.
Можна вважати, що ні пошук, ні підняття скарбу у печері, ні переміщення печерою не споживають повітря.
Кожен набір тестів складається з декількох тестових випадків. Файл починається з одного числа (0 < t \leq 2000) в окремому рядку, що означає кількість тестових випадків у файлі. Кожен тестовий випадок починається з двох цілих чисел та в одному рядку, де — кількість печер, а — кількість тунелів у мережі (1 \leq n \leq 10000, 0 \leq m \leq 50000). Далі йде рядків із описом тунелів у вигляді трьох цілих чисел , та , де , — номери печер, а — кількість повітря, необхідна для занурення через цей тунель (0 \leq a, b < n, 0 \leq l \leq 500). Після тунелів іде ціле число в окремому рядку — кількість ідолів у системі печер (0 \leq i \leq 8). Далі в одному рядку вказано цілих чисел p_1, \ldots, p_i, які позначають печери з ідолами (0 \leq p_1, \ldots, p_i < n). Введення завершується одним числом, що вказує кількість літрів повітря, які у тебе є (0 \leq a \leq 1000000). Ти завжди починаєш (і закінчуєш) у печері з номером .
Для кожного тестового випадку виведи одне число в окремому рядку, де — максимальна кількість ідолів, які дайвер може врятувати.
Приклад 1