Cable TV
A huge telephone company is planning to reuse its already installed, unused wires for a brand new cable TV channel. The company’s future income depends on three main factors:
- The running cost of TV channel (we denote it by R),
- the TV charges (we will denote it by H), which are, of course, affected by the number of units connected together in the cable TV (we denote it by U), and
- the cost of used connection maintenance (we denote it by M).
All units of the cable TV must be connected together. Units are connected together if there is at least one path between every two units. The path is defined as usual by a sequence of two-unit connections. Every two-unit connection is always bidirectional. Conditions of cable TV service are changing every hour due to unstable economic situation. Fortunately, the company can operate with very confidential parametric functions for forecast calculations. The income is calculated as H(U,t) - M(t) - R(t), where
- t is defined as the positive integer number of hours that have elapsed (t starts from 0);
- R(t)=A⨯(10^{6} + t⨯B)⨯10^{-6};
- H(U,t)= U⨯C⨯(10^{6} + t⨯B)⨯10^{-6};
- M(t)=Sum of all used two-unit connection maintenance costs on the time t (we will denote two-unit connection from m to n on the time t by E(m,n,t));
- E(m,n,t)= ((m⨯(n+1)) mod D)+((m⨯n) mod (D+1)) + ∑_{i=1..t}(10^{-6}⨯((i + m + i⨯n) mod D)) where 0 ≤ m < n < N;
- E(m,n,t) represents the cost of maintenance of two-unit bidirectional connection from m to n on time represented by t;
- A, B, C and D are positive integer constants that do not exceed 10^{6} and B⨯C > D + A⨯B;
- N is the maximum number of all units that can be possible considered for the cable TV where 0 < N ≤ 10^{3}.
For a further analysis, the management of the company wants to know the lowest time t when the planned income will cross over a defined threshold L for some positive U and thus according to connections of U units.
Input
The Input contains six lines with integers N,A,B,C,D,L.
Output
The output contains one line with the lowest t that the income is greater
than L for some positive U where 0 < U ≤ N.
If there is no such t from 0 to 100000, then the program will return one
line with text “NO SOLUTION FOUND!
”.
Examples
Input:
20 1 10000 2 9999 19
Output:
0
Input:
200 5 10 6 5 1200
Output:
426
Input:
20 4 10 6 5 200
Output:
74271
Input:
1000 5 9 6 5 5996
Output:
19