Для того щоб звільнити царівну Котигорошко має перемогти злого чаклуна, подолавши ~N~ світів, кожен з яких має ~N~ етапів. Етапи можна подолати лише у певному порядку. Перший етап знаходиться у першому світі. Наступний етап після ~j~-го в ~i~-му світі описується наступним чином:

• Якщо ~j < N~, то наступний етап – це (~j+1~)-й етап в ~i~-му світі.
• Якщо ~i < N, j = N~, то наступний етап – це 1-й етап в (~i+1~)-му світі.
• Якщо ~i = N, j = N~, то наступного етапу немає, і всі світи чаклуна пройдені.

Назва ~j~-го етапу в ~i~-му світі записується так: ~i-j~ (без пропусків).

Наприклад, назва першого етапу - ~1-1~, а назва останнього етапу - ~8-8~.

Відомо, що Котигорошко зараз знаходиться на етапі ~S~. Виведіть назву наступного етапу, який має пройти Коригорошко.

Обмеження

• ~1 \le N \le 100~
• ~S~ – містить лише цифри та '-'.
• ~S~ – не містить назви останнього етапу.

Input

Перший рядок містить ціле число ~N~.

Другий рядок містить назву етапу ~S~, на якому знаходиться Котигорошко.

Output

Вивести назву наступного етапу Котигорошка.

Sample Input 1

8
4-2

Sample Output 1

4-3

Sample Input 2

8
1-8

Sample Output 2

2-1

Sample Input 3

5
3-3

Sample Output 3

3-4

Публікація у Facebook вважається популярнішою, якщо кількість лайків під нею чітко перевищує кількість лайків під іншою публікацією. Якщо кількість лайків однакова, то публікація з більшою кількістю коментарів є популярнішою.

Дано масиви ~A~ та ~B~ розмірністю ~N~. ~A_i~ містить кількість лайків до ~i~-допису, а ~B_i~ містить кількість коментарів до ~i~-допису.

Знайдіть найбільш популярну публікацію.

Гарантується, що кількість коментарів до всіх публікацій буде різною.

Обмеження

• ~1 \le N \le 10^5~
• ~1 \le A_i, B_i \le 2 \cdot 10^5~
• Масив ~B~ містить різні цілі числа

Input

Перший рядок містить ціле число ~N~.

Другий рядок містить ~N~ цілих чисел ~A_i~.

Третій рядок містить ~N~ цілих чисел ~B_i~.

Output

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

Sample Input 1

3
5 4 4
1 2 3

Sample Output 1

1

Sample Input 2

3
10 10 9
2 5 4

Sample Output 2

2

Sample Input 3

3
3 3 9
9 1 3

Sample Output 3

3

Sample Input 4

4
2 8 1 5
2 8 1 9

Sample Output 4

2

Вам дано чорно-біле зображення, яке представлене у вигляді двовимірного масиву розміром ~m \times n~. Кожна клітинка масиву є пікселем, і вона може мати два значення:

• 1 - білий піксель.
• 0 - чорний піксель.

Ваше завдання - порахувати кількість "об'єктів" на цьому зображенні. Об'єктом вважається окремий білий піксель або зв'язана група білих пікселів. Два пікселі вважаються зв'язаними, якщо вони є сусідами по горизонталі, вертикалі або діагоналі.

Обмеження

• ~1 \le n,m \le 1000~

Input

Перший рядок містить два цілих числа ~m~ та ~n~ - розміри зображення по висоті та ширині. В наступних m рядках міститься по n чисел - лише 0 та 1.

Output

Вихідні дані: Одне ціле число - загальна кількість об'єктів на зображенні.

Sample Input 1

4 5
1 1 0 0 0
0 1 0 1 1
0 0 0 1 0
1 0 0 0 0

Sample Output 1

3

Notes

Перший об'єкт: складається з пікселів на позиціях (0,0), (0,1) та (1,1). Вони зв'язані між собою.

Другий об'єкт: складається з пікселів на позиціях (1,3) та (1,4). Вони зв'язані. Піксель (2,3) також є частиною цього об'єкта, оскільки він зв'язаний з пікселем (1,3) по вертикалі.

Третій об'єкт: складається лише з одного пікселя на позиції (3,0).

Назвемо послідовність довжини ~N~ з двох цілих чисел ~A~ і ~B~ магічною, якщо в ній будь-яка підпослідовність з двох або більше однакових чисел має парну довжину.

Необхідно порахувати кількість таких магічних послідовностей.

Обмеження

- ~1 \le N, A, B \le 32~

Input

Три цілих числа: N, A, B

Output

Одне ціле число — кількість таких послідовностей.

Sample Input 1

3 1 2

Sample Output 1

6

Notes

~N~=3, числа, які можна використовувати: 1 та 2.

Перелічимо всі можливі послідовності та перевіримо їх:

• [1, 1, 1] — Недопустимо (три одиниці поспіль).
• [1, 1, 2] — Допустимо (дві одиниці, одна двійка).
• [1, 2, 1] — Допустимо (одиниці та двійка поодинці).
• [1, 2, 2] — Допустимо (одиниця, дві двійки).
• [2, 1, 1] — Допустимо.
• [2, 1, 2] — Допустимо.
• [2, 2, 1] — Допустимо.
• [2, 2, 2] — Недопустимо.

Загальна кількість допустимих послідовностей — 6.

Степан повернувся з ярмарку настільних ігор. Він приніс додому ~N~ ігор. Перш ніж грати в гру, необхідно вивчити її правила. Вивчення правил ~i~-ї гри займає ~P_i~ хвилин. Після вивчення правил можна грати в гру. Гра в ~i~-ту гру займає ~T_i~ хвилин. Кожна гра також має свій власний рейтинг ~R_i~.

У найближчі дні Степан планує витратити щонайбільше D хвилин на настільні ігри. Який максимальний рейтинг зможе отримати Степан?. У кожну гру можна грати довільну кількість разів.

Обмеження

• ~1 \le N,D \le 5000~
• ~0 \le P_i \le 5000~
• ~1 \le T_i \le 5000~
• ~1 \le R_i \le 10^9~

Input

Перший рядок містить цілі числа ~N~ та ~D~ - кількість ігор та час, запланований на гру.

Далі ідуть ~N~ рядків, які містить цілі числа ~P_i~, ~T_i~ та ~R_i~ - час, необхідний для вивчення правил, час, необхідний для гри, та рейтинг ~i~-ї гри.

Output

Вивести максимальний прогнозований рейтинг Степана.

Scoring

• 15 балів при ~N~ = 1
• 25 балів при ~N \le 10~
• 25 балів при ~P_i = 0~
• 35 балів без додаткових обмежень

Sample Input 1

3 10
2 3 5
5 1 5
3 2 5

Sample Output 1

25

Sample Input 2

4 13
0 6 5
0 3 4
0 2 3
0 4 4

Sample Output 2

19

Sample Input 3

3 10
1 1 1
3 2 3
2 3 5

Sample Output 3

11