루미의 스트레스 해소하기

28번째 생일을 맞이할 때까지도 여전히 연애를 하지 못한 루미는 많은 스트레스를 받았다. 그런 루미를 불쌍히 여긴 친구들은 루미가 좋아할 만한 여러 활동을 소개해 주었다. 루미는 그 중 몇 개를 취미로 삼아 스트레스를 해소하고자 한다.

각 취미는 루미의 시간과 체력을 소모하며 루미의 스트레스 수치를 줄여준다. 루미는 한 가지 취미를 여러 번 즐길 수 있다. 하지만 루미의 체력이 임계 체력 이하로 떨어질 경우 스트레스 해소량이 줄어들거나 오히려 스트레스 수치가 늘어날 수도 있다. 지루한 걸 싫어하는 루미는 취미 활동을 하지 않을 때는 매 시간 $F$ 만큼의 스트레스 수치가 증가하게 된다. 취미를 즐긴 후 체력이 음수가 되거나 즐긴 취미 활동의 시간 합이 루미의 가용 시간을 넘기면 그 취미를 즐길 수 없다.

임계 체력 $D$, 스트레스 증가 지수 $E$인 루미가 스트레스 해소량 $L$, 체력 소모량 $M$인 취미를 시작한 시점에서의 현재 스트레스 수치 $A$, 현재 체력 $C_{cur}$일 때 실제로 스트레스 수치가 감소하는 양인 $L_{eff}$는 다음과 같다. \[L_{eff}=\begin{cases}{L}&{(C_{cur} \gt D)}\\{\left\lfloor L\times\left( 1-\frac{E}{100} \right) \right\rfloor}&{(C_{cur} \le D)}\\\end{cases}\] 취미 활동 후 스트레스 수치는 $\max (0,A-L_{eff})$이 되고, 체력은 $C_{cur}-M$이 된다.

루미는 최근 너무 많은 스트레스를 받았기 때문에 스트레스 수치를 최대한 줄이기로 했다. 하지만 가능한 스트레스 수치의 최솟값을 찾는 것 또한 스트레스를 받는 일이기 때문에 당신이 그 스트레스 수치의 최솟값을 대신 찾아야 한다.

첫 번째 줄에 취미의 개수 $N$, 루미의 초기 스트레스 수치 $A$, 가용 시간 $B$, 초기 체력 $C$, 임계 체력 $D$, 스트레스 증가 지수 $E$, 단위 시간당 스트레스 수치 증가량 $F$가 공백으로 구분되어 주어진다.

두 번째 줄부터 $N$개의 줄에 걸쳐 각 취미의 스트레스 해소량 $L$, 소모 시간 $H$, 체력 소모량 $M$이 공백으로 구분되어 주어진다.

$B$시간 뒤 가능한 루미의 스트레스 수치의 최솟값을 출력한다.

• $1\leq N\leq 100$
• $0\leq A\leq 3\, 290$
• $1\leq B,C\leq 1\, 000$
• $0\leq D<C$
• $0\leq E\leq 200$
• $0\leq F\leq 100$
• $0\leq L\leq 1\, 000$
• $1\leq H,M\leq 1\, 000$
• 입력으로 주어지는 모든 수는 정수이다.