Дмитрик хоче купити популярну ігрову консоль. Є \(N\) магазинів, які продають її: магазини пронумеруємо \(1, 2, \dots, N\). Магазин \(i\) – це \(A_i\) хвилин ходьби від місця, де зараз знаходиться Дмитрик, продає гру за \(P_i\), і наразі має \(X_i\) штук на складі. Тепер Дмитрик піде до одного з цих магазинів пішки і придбає гру, якщо вона все ще буде в наявності, коли він туди прийде. Однак ця гра настільки популярна, що кількість консолей на складі (якщо є) у кожному магазині зменшиться на 1 у наступні моменти: \(0.5, 1.5, 2.5, \dots \) хвилин.

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

Формат вхідних даних

Перший рядок містить ціле число \(N\) (\(1 \le N \le 10^5\))

Наступні  \(N\) рядків містять цілі числа \(A_i, P_i, X_i\) (\(1 \le A_i, P_i, X_i \le 10^9\))

Числа у рядках розділяються пропуском.

Формат вихідних даних

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

Примітка

До прикладу 1:

Якщо він піде до магазину 1, у ньому буде 2 гри, коли він туди потрапить і він може купити одну за 9 грн.

Якщо він піде до магазину 2, у ньому буде 1 гра, коли він туди потрапить і він може купити одну за 8 грн.

Якщо він піде до магазину 3, гри не буде в наявності, коли він туди потрапить; він не може його купити.

Приклад вхідних даних

3
3 9 5
4 8 5
5 7 5

Приклад вихідних даних

8

Приклад вхідних даних

3
5 9 5
6 8 5
7 7 5

Приклад вихідних даних

-1

Приклад вхідних даних

10
158260522 877914575 602436426
24979445 861648772 623690081
433933447 476190629 262703497
211047202 971407775 628894325
731963982 822804784 450968417
430302156 982631932 161735902
880895728 923078537 707723857
189330739 910286918 802329211
404539679 303238506 317063340
492686568 773361868 125660016

Приклад вихідних даних

861648772