Description

Given $7$ integers $N, A_0, B_0, L_0, A_1, B_1, L_1$, you are asked to design a binary string $S = s_1 s_2 \ldots s_i \ldots s_N$ that satisfies:

1. $s_i = 0$ or $s_i = 1$, $1 \leq i \leq N$.
2. For any consecutive substring of $S$ with length $L_0$, namely $s_j s_{j+1} \ldots s_{j+L_0-1}$ ($1 \leq j \leq N - L_0 + 1$), the number of $0$s is at least $A_0$ and at most $B_0$.
3. For any consecutive substring of $S$ with length $L_1$, namely $s_j s_{j+1} \ldots s_{j+L_1-1}$ ($1 \leq j \leq N - L_1 + 1$), the number of $1$s is at least $A_1$ and at most $B_1$.

For example, if $N = 6, A_0 = 1, B_0 = 2, L_0 = 3, A_1 = 1, B_1 = 1, L_1 = 2$, then there exists a binary string $S = 010101$ that satisfies all the above conditions.

Input Format

Only one line containing $7$ integers, in order: $N, A_0, B_0, L_0, A_1, B_1, L_1$ ($3 \leq N \leq 1000$, $1 \leq A_0 \leq B_0 \leq L_0 \leq N$, $1 \leq A_1 \leq B_1 \leq L_1 \leq N$). Adjacent integers are separated by one space.

Output Format

Only one line. If there is no binary string satisfying all conditions, output the integer -1. Otherwise, output the maximum possible number of $1$s among all binary strings that satisfy all conditions.

6 1 2 3 1 1 2

3

Hint

Translated by ChatGPT 5