eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Східний кросворд

Східний кросворд

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Марися любить розв’язувати східні кросворди. Так називається головоломка, в якій потрібно зафарбувати деякі клітинки прямокутника N * M таким чином, щоб на кожній з N вертикалей і на кожній з M горизонталей кількість зафарбованих клітинок дорівнювала деякому наперед визначеному записаному на полях для даної вертикалі чи горизонталі числу. На жаль, інколи укладачі кросвордів помиляються, і кросворд розв’язку не має. Дівчина не хотіла б марнувати свій час, розв’язуючи такі кросворди.

Завдання

Напишіть програму, яка для заданих величин N та M, а також N +M чисел, записаних на полях кросворда, визначить, чи є даний кросворд розв’язним.

Вхідні дані

У першому рядку вхідного файла записано число 1 ≤ T ≤ 5, — кількість кросвордів для перевірки. Кожен кросворд подається трьома рядками: в першому рядку записано натуральні числа M та N, що не перевищують 10^5, — ширину та висоту кросворда; у другому рядку подано N цілих невід’ємних чисел — кількість зафарбованих клітинок на першій, другій, ...,N -й вертикалях відповідно; у третьому рядку подано M цілих невід’ємних чисел — кількість зафарбованих клітинок на першій, другій, ..., M -й горизонталях відповідно. Жодне з чисел у другому і третьому рядках не перевищує загальної кількості клітинок на відповідній вертикалі чи горизонталі.

Вихідні дані

Вихідний файл повинен містити відповідь для кожного з кросвордів в окремому рядку: 1, якщо кросворд розв’язний, або 0, якщо ні. Відповіді потрібно подати в тому ж порядку, в якому у вхідному файлі подано самі кросворди.

Приклад

Вхідні дані #1
2
3 2
1 2 1
2 2
4 5
5 5 5 5
0 0 0 0 0
Вихідні дані #1
1
0

Оцінювання

Набір тестів складається з 3 блоків, для яких додатково виконуються такі умови:

1. 15 % балів: жоден з розмірів (ні ширина, ні висота) жодного з кросвордів не перевищує 5.

2. 35 % балів: жоден з розмірів жодного з кросвордів не перевищує 1000, причому хоча б один з розмірів хоча б одного з кросвордів більший за 5.

50 % балів: хоча б один з розмірів хоча б одного з кросвордів більший за 1000.

Пояснення. У першому випадку кросворд має, наприклад, таке розв’язання:

У другому випадку кросворд нерозв’язний: з одного боку, рядок з п’ятірок свідчить, що всі вертикалі повністю зафарбовано; з іншого боку, рядок з нулів означає, що жодна з горизонталей не містить жодної зафарбованої клітинки. Такого, очевидно, бути не може.

Автор Данило Мисак
Джерело XXVIII Всеукраїнська олімпіада з інформатики 2015 р.