Тренер з спортивного програмування хоче визначити кращу команду минулого року. У нього є список учнів по командах, які перемагали у турнірах на протязі року. Склад команд часто змінювався, але кількість учнів у команді завжди була рівна трьом. Необхідно визначити найбільшу кількість перемог, які отримала одна із команд. Порядок імен у команді довільний.

Input

Перший рядок містить ~N~ (~1 \le N \le 1000~)- кількість турнірів.

Наступні ~N~ рядків містять список учнів у команді, яка перемогла у i-му турнірі. Ім'я учня - одне слово, довжиною не більше 255 символів. Імена у рядку розділені пропуском.

Output

Вивести одне число, найбільшу кількість перемог, які отримала одна із команд.

Sample Input 1

5
KLYM SIR VIZYR
DANA KOLYAN SIR
VIZYR KLYM SIR
OKSI KLYM VIZYR
VIZYR SIR KLYM

Sample Output 1

3

Notes

Команда (KLYM,SIR,VIZYR) перемагала три рази.

На уроці фізкультури ~N~ учнів стоять в один ряд, кожен має свою позицію(координату). Вони грають гру: кидають м'яч із рук в руки сусіду справа.

Група з трьох учнів (~X~,~Y~,~Z~) робить два успішні кидки. Учень ~X~ кидає м'яч вправо до учня ~Y~, а потім учень ~Y~ кидає його до учня ~Z~. Другий кидок виходить успішним на відстань не меншу, ніж перша і не більшу, ніж подвоєна перша. Треба порахувати кількість можливих груп учнів, які здійснили успішні кидки.

Input

Перший рядок містить кількість учнів ~3 \le N \le 1000~.

Наступні ~N~ рядків містять координату учня з проміжку ~0..100 000 000~

Output

Одне число - кількість груп учнів (~X~,~Y~,~Z~), де ~Y~ стоїть праворуч ~X~, а ~Z~ стоїть праворуч ~Y~ і відстань від ~Y~ до ~Z~ знаходиться між ~XY~ і ~2*XY~ (включно), де ~XY~ відстань від ~X~ до ~Y~.

Scoring

• При ~N \le 500~ - 50 балів,
• при ~ N \le 1000~ - 50 балів

Sample Input 1

5
3
1
10
7
4

Sample Output 1

4

Notes

Відповідно до вхідних даних є три можливі трійки учнів: 1-3-7, 1-4-7, 1-4-10, 4-7-10.

Бізнес-план деякої компанії містить ~N~ мініпроєктів, які при вчасному виконанні принесуть прибуток. І-й проєкт дасть прибуток ~Q_i~, якщо його виконати до часу ~T_i~.

Напишіть програму, яка визначить максимальний прибуток компанії при оптимальному виконанні мініпроєктів. Ваша програма починає працювати при t=0.

Input

Перший рядок містить ~N~ (~1 \le N \le 10000~)

Наступні ~N~ рядків містять прибуток та час завершення для кожного мініпроєкту: ~Q_i~, ~T_i~ (~1 \le Q_i \le 1000, 1 \le T_i \le 10000~)

Output

Вивести одне число - максимальний прибудок від реалізації мініпроектів.

Scoring

• при ~N \le 30~ - 21 бал,
• при ~N \le 3 000~ - 27 балів,
• при ~N \le 10 000~ - 52 бали

Sample Input 1

4
10 3
7 5
8 1
2 1

Sample Output 1

25

Notes

Спочатку реалізовуємо проєкт 3(4-й ігноруємо). Потім виконуємо проєкти 1 та 2.

Компанія Air Glob планує з'єднати повітряним сполученням ~N~ міст країни. Аеропорти перенумеровані від 1 до ~N~ і у перших ~K~ аеропортах можливі пересадки. На даний момент є ~M~ однонаправлених маршрутів. Політ ~i~ відбувається з аеропорту ~U_i~ до ~V_i~ з ціною ~D_i~ у.о.

Авіакомпанія отримала замовлення на ~Q~ подорожей. Подорож ~i~ з аеропорту ~A_i~ до ~B_i~ може складатися із довільної кількості прямих перельотів, (навіть можливий варіант із відвідуванням одного із аеропортів декілька разів) але є обов'язковим відвідування хоча би одного аеропорту з пересадкою, який може бути не стартовим і не кінцевим. Отже, не гарантується, що є коректним маршрут від ~A_i~ до ~B_i~.

Завдання: необхідно знайти мінімальну вартість подорожей для всіх коректних маршрутів.

Input

Перший рядок містить чотири цілих числа: ~N~, ~M~, ~K~, ~Q~ (~1 \le N \le 200, 1 \le K \le 100, 1 \le M,Q \le 10000~). Рядки від 2 до ~M+1~: ~U_i~, ~V_i~, ~D_i~ (~1 \le D_i \le 1000000~).

Наступні ~Q~ рядків містять варіанти подорожей ~A_i~, ~B_i~.

Output

У першому рядку вивести кількість коректних маршрутів, а в другому - їх мінімальну вартість.

Scoring

Кожен тест оцінюється окремо

Sample Input 1

3 3 1 3
3 1 10
1 3 10
1 2 7
3 2
2 3
1 2

Sample Output 1

2
24

Notes

Подорож із 3 в 2 можна здійснити єдиним способом із вартістю 10+7. Маршрут із 2 в 3 є некоректним. Політ із 1 в 2 можливий і його вартість рівна 7.

Компанія Air Glob планує з'єднати повітряним сполученням ~N~ міст країни. Аеропорти перенумеровані від 1 до ~N~ і у ~K~ аеропортах можливі пересадки. Компанія пропонує ~M~ однонаправлених польотів.

Політ ~i~ відбувається з аеропорту ~U_i~ до ~V_i~ з ціною ~D_i~ у.о. Для кожного польоту або в ~U_i~, або в ~V_i~ можлива пересадка. Існує не більше одного польоту між будь якими двома аеропортами в заданому напрямку, і не існує польоту, який починається та закінчується на одному аеропорту.

Авіакомпанія отримала ~Q~ запитів на однонаправлене перевезення туристів. ~І~-й запит - це політ з аеропорту ~A_i~ до ~B_i~. Необхідно визначити, чи можна видати квиток на переліт з ~A_i~ до ~B_i~ та його мінімальну вартість.

Для скорочення виведення інформації ваша програма має вивести загальну кількість квитків, які можна видати, та мінімальну їх сумарну вартість.

Input

Перший рядок містить чотири цілих числа: ~N~, ~M~, ~K~, ~Q~ (~1 \le N \le 20000~, ~1 \le K \le 200, K \le N~, ~1 \le M \le 20000~, ~1 \le Q \le 50000~).

Рядки від 2 до ~M+1~: ~U_i~, ~V_i~, ~D_i~ (~1 \le D_i \le 10000~).

Далі ідуть ~K~ рядків, що містять номери аеропортів із пересадками.

Наступні ~Q~ рядків містять запити на перевезення з ~A_i~ до ~B_i~.

Output

У першому рядку вивести кількість квитків, які можуть бути видані, а у другому - їх сумарну мінімальну вартість.

Scoring

Оцінюється кожен тест окремо.

Sample Input 1

3 3 1 2
1 2 10
2 3 10
2 1 5
2
1 3
3 1

Sample Output 1

1
20

Notes

Для першого запиту є тільки один маршрут 1->2->3 з ціною 20. З 3-го аеропорту маршрутів не існує.