Як карта ляже

Обмеження: 2 сек., 512 МіБ

Зеник — відомий картяр. Марічці стало цікаво, чи справді він такий вправний, тож вона запропонувала йому парі.

Зеник отримує \(n\) карт у руку, а на столі лежить колода з \(m\) карт. На кожній карті записано додатне ціле число або символ *. Щоб виграти парі, Зеник має розіграти рівно \(k\) карт із руки та набрати не більше ніж \(s\) очок.

На початку ходу Зеник має нуль очок. Він вибирає рівно \(k\) карт із руки та розігрує кожну з них за такими правилами:

• Якщо на карті записано число, воно додається до суми очок.

• Якщо на карті записано *, Зеник бере верхню карту з колоди та також розігрує її за цими правилами. Якщо взята карта також містить *, Зеник бере наступну карту з колоди.

Усі взяті з колоди карти вилучаються з неї та не можуть бути використані повторно. Карти, взяті з колоди, не враховуються до \(k\) вибраних карт із руки. Гарантується, що числових карт у колоді вистачить, щоб завершити хід за будь-якого вибору \(k\) карт із руки.

Зеник знає, які карти є в колоді, але не знає їхнього порядку. Допоможіть йому визначити, чи можна вибрати рівно \(k\) карт із руки так, щоб виграти парі за будь-якого порядку карт у колоді.

Вхідні дані

У першому рядку задано чотири цілі числа \(n\), \(m\), \(k\) і \(s\) — кількість карт у руці, кількість карт у колоді, кількість карт, які потрібно вибрати з руки, та максимальна дозволена сума очок відповідно.

У другому рядку задано \(n\) розділених пробілами значень, які описують карти в руці. Кожне значення — це символ * або додатне ціле число.

У третьому рядку задано \(m\) розділених пробілами значень, які описують карти в колоді. Кожне значення має такий самий формат. Порядок значень у цьому рядку не визначає порядок карт у колоді.

Вихідні дані

У єдиному рядку виведіть TAK, якщо Зеник може вибрати рівно \(k\) карт із руки так, щоб сума очок не перевищила \(s\) за будь-якого порядку карт у колоді, або NI, якщо це неможливо.

Обмеження

\(1 \le k \le n \le 2 \cdot 10^5\),

\(1 \le m \le 2 \cdot 10^5\),

\(1 \le s \le 10^9\),

кожне число на карті належить проміжку \([1, 1000]\),

кількість числових карт у колоді не менша за \(\min(k, a)\), де \(a\) — кількість карт із символом * у руці.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
6 4 3 10 * 2 10 * 8 * 1 5 3 *	TAK

Примітки

У прикладі Зеник може вибрати карту з числом 2 і дві карти *. Незалежно від порядку колоди буде додано не більше ніж \(5+3\) за числові карти з колоди. Отже, загальна сума очок не перевищить \(2+5+3=10\), і Зеник виграє парі.