| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 1 | 1 | 1 | 100.000% |
Как известно, у Черной Жемчужины два капитана: капитан Джек Воробей и Барбосса. Корабль содержит ровно $n$ пушек, расположенных в ряд. Во время боя оба капитана раз в минуту одновременно дают команды своим матросам. Команды бывают следующих видов:
send $l$ $r$ --- послать своих матросов стрелять из пушек с номерами от $l$ до $r$ включительноback $l$ $r$ --- отозвать всех своих матросов с пушек с номерами от $l$ до $r$ включительно. Если на каких-то пушках из этого отрезка нет матросов, подчиняющихся этому капитану, то с такими пушками ничего не происходитrum --- принести еще одну бутылку ромаКаждая команда выполняется мгновенно, после чего сражение идет еще минуту до следующей команды. Если в какой-то момент у одной и той же пушки окажутся матросы, подчиняющиеся разным капитанам, они подерутся и убьют друг друга. Эта ситуация не устраивает никого из капитанов, и поэтому они обратились к вам с просьбой помочь им в решении этой проблемы.
Перед началом очередного сражения капитан Джек Воробей и Барбосса составили планы своих действий. Известно, что план капитана Джека Воробъя состоит из $m_1$ команд, а план Барбоссы --- из $m_2$ команд. В начале $i$-ой минуты боя каждый капитан дает своим матросам $i$-ую команду из своего плана, если в нем есть хотя бы $i$ команд. Вам поручили исправить планы так, чтобы все матросы остались живы. Единственная доступная вам модификация плана сражения --- вставка нескольких команд rum в любые места. Понятно, что капитаны не очень любят менять свои планы, поэтому суммарное количество команд, добавленных Вами в оба плана, должно быть минимально.
В первой строке дано число $n$ --- количество пушек на корабле (1ドル \le n \le 10^9$).
Во второй строке задано число $m_1$ --- количество команд в плане Джека Воробья (1ドル \le m_1 \le 3{,円}000$). В следующих $m_1$ строках перечислены команды из плана Джека Воробья. Команды заданы так, как они описаны выше. Для всех команд, использующих $l$ и $r,ドル верно, что 1ドル \le l \le r \le n$. Гарантируется, что последняя команда в плане --- back 1 $n$.
Во следующей строке задано число $m_2$ --- количество команд в плане Барбоссы (1ドル \le m_2 \le 3{,円}000$). В следующих $m_2$ строках перечислены команды из плана Барбоссы. Команды заданы так, как они описаны выше. Для всех команд, использующих $l$ и $r,ドル верно, что 1ドル \le l \le r \le n$. Гарантируется, что последняя команда в плане --- back 1 $n$.
В единственной строке выведете минимальное количество дополнительных команд.
3 4 send 1 1 send 2 2 back 1 1 back 1 3 5 send 2 3 send 1 1 back 2 2 rum back 1 3
3