Problem: Only T milliseconds left before the start of well-known online programming contest Codehorses Round 2017.

Polycarp needs to download B++ compiler to take part in the contest. The size of the file is f bytes.

Polycarp's internet tariff allows to download data at the rate of one byte per t0 milliseconds. This tariff is already prepaid, and its use does not incur any expense for Polycarp. In addition, the Internet service provider offers two additional packages:

  * download a1 bytes at the rate of one byte per t1 milliseconds, paying p1 burles for the package; 
  * download a2 bytes at the rate of one byte per t2 milliseconds, paying p2 burles for the package. 



Polycarp can buy any package many times. When buying a package, its price (p1 or p2) is prepaid before usage. Once a package is bought it replaces the regular tariff until package data limit is completely used. After a package is consumed Polycarp can immediately buy a new package or switch to the regular tariff without loosing any time. While a package is in use Polycarp can't buy another package or switch back to the regular internet tariff.

Find the minimum amount of money Polycarp has to spend to download an f bytes file no more than in T milliseconds.

Note that because of technical reasons Polycarp can download only integer number of bytes using regular tariff and both packages. I.e. in each of three downloading modes the number of downloaded bytes will be integer. It means that Polycarp can't download a byte partially using the regular tariff or/and both packages.

Input

The first line contains three integer numbers f, T and t0 (1 ≤ f, T, t0 ≤ 107) — size of the file to download (in bytes), maximal time to download the file (in milliseconds) and number of milliseconds to download one byte using the regular internet tariff.

The second line contains a description of the first additional package. The line contains three integer numbers a1, t1 and p1 (1 ≤ a1, t1, p1 ≤ 107), where a1 is maximal sizes of downloaded data (in bytes), t1 is time to download one byte (in milliseconds), p1 is price of the package (in burles).

The third line contains a description of the second additional package. The line contains three integer numbers a2, t2 and p2 (1 ≤ a2, t2, p2 ≤ 107), where a2 is maximal sizes of downloaded data (in bytes), t2 is time to download one byte (in milliseconds), p2 is price of the package (in burles).

Polycarp can buy any package many times. Once package is bought it replaces the regular tariff until package data limit is completely used. While a package is in use Polycarp can't buy another package or switch back to the regular internet tariff.

Output

Print the minimum amount of money that Polycarp needs to pay to download B++ compiler no more than in T milliseconds. If there is no solution, print the only integer -1.

Examples

Input

120 964 20
26 8 8
13 10 4


Output

40


Input

10 200 20
1 1 1
2 2 3


Output

0


Input

8 81 11
4 10 16
3 10 12


Output

28


Input

8 79 11
4 10 16
3 10 12


Output

-1

Note

In the first example Polycarp has to buy the first additional package 5 times and do not buy the second additional package. He downloads 120 bytes (of total 26·5 = 130 bytes) in 120·8 = 960 milliseconds (960 ≤ 964). He spends 8·5 = 40 burles on it.

In the second example Polycarp has enough time to download 10 bytes. It takes 10·20 = 200 milliseconds which equals to upper constraint on download time.

In the third example Polycarp has to buy one first additional package and one second additional package.

In the fourth example Polycarp has no way to download the file on time.

Solution (in JAVA):

Solution:
/*
 * Author Ayub Subhaniya
 * Institute DA-IICT
 */
 
import java.io.*;
import java.math.*;
import java.util.*;
 
 
public class Codeforces429D
{
	
	InputStream in;
	PrintWriter out;
	
	long MAX=Long.MAX_VALUE;
	void solve() 
	{
		long f=nl();
		long T=nl();
		long t0=nl();
		long a1,t1,p1,a2,t2,p2;
		a1=nl();t1=nl();p1=nl();
		a2=nl();t2=nl();p2=nl();
		
		long max1=f/a1;
		long max2=f/a2;
		long cost=MAX;
		
		if (t1<t2)
		{
			for (int k1=0;k1<=max1;k1++)
			{
				long sz=f-k1*a1;
				
				long l=0,r=sz/a2,result=-1,t=a1*k1*t1;
				long td;
				while (l<=r)
				{
					long mid=((l+r)>>1);
					td=a2*mid;
					if (t+td*t2+(sz-td)*t0 <= T)
					{
						result=mid;
						r=mid-1;
					}
					else
					{
						l=mid+1;
					}
				}
				
				if (t+sz*t2<=T)
					cost=Math.min(cost, k1*p1+((sz+a2-1)/a2)*p2);
				
				if (result!=-1)
				{
					cost=Math.min(cost, k1*p1+result*p2);
				}
				
			}
			
			if (f*t1<=T)
				cost=Math.min(cost, ((f+a1-1)/a1)*p1);
		}
		else
		{
			for (int k2=0;k2<=max2;k2++)
			{
				long sz=f-k2*a2;
				
				long l=0,r=sz/a1,result=-1,t=a2*k2*t2;
				long td;
				while (l<=r)
				{
					long mid=((l+r)>>1);
					td=a1*mid;
					if (t+td*t1+(sz-td)*t0<=T)
					{
						result=mid;
						r=mid-1;
					}
					else
					{
						l=mid+1;
					}
				}
				
				if (t+sz*t1<=T)
					cost=Math.min(cost, k2*p2+((sz+a1-1)/a1)*p1);
				
				if (result!=-1)
				{
					cost=Math.min(cost, k2*p2+result*p1);
				}
				
			}
			
			if (f*t2<=T)
				cost=Math.min(cost, ((f+a2-1)/a2)*p2);
		}
		
		if (cost==MAX)
			out.println(-1);
		else
			out.println(cost);
	}
		
	void run() throws Exception 
	{
		String INPUT = "C:/Users/ayubs/Desktop/input.txt";
		in = oj ? System.in : new FileInputStream(INPUT);
		out = new PrintWriter(System.out);
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		tr(System.currentTimeMillis() - s + "ms");
		
	}
	public static void main(String[] args) throws Exception 
	{
		new Codeforces429D().run();
	}
	
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;
	
	private int readByte() 
	{
		if (lenbuf == -1)
			throw new InputMismatchException();
		if (ptrbuf >= lenbuf) 
		{
			ptrbuf = 0;
			try 
			{
				lenbuf = in.read(inbuf);
			}
			catch (IOException e) 
			{
				throw new InputMismatchException();
			}
			if (lenbuf <= 0)
				return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private boolean inSpaceChar(int c) 
	{
		return !(c >= 33 && c <= 126);
	}
	
	private int skip() 
	{
		int b;
		while ((b = readByte()) != -1 && inSpaceChar(b))
			;
		return b;
	}
	
	private double nd() 
	{
		return Double.parseDouble(ns());
	}
	
	private char nc() 
	{
		return (char) skip();
	}
	
	private String ns() 
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while (!(inSpaceChar(b))) 
		{ // when nextLine, (inSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private char[] ns(int n) 
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while (p < n && !(inSpaceChar(b))) 
		{
			buf[p++] = (char) b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private char[][] nm(int n, int m) 
	{
		char[][] map = new char[n][];
		for (int i = 0; i < n; i++)
			map[i] = ns(m);
		return map;
	}
	
	private int[] na(int n) 
	{
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}
	
	private int ni() 
	{
		int num = 0, b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') 
		{
			minus = true;
			b = readByte();
		}
		
		while (true) 
		{
			if (b >= '0' && b <= '9') 
			{
				num = num * 10 + (b - '0');
			} 
			else 
			{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private long nl() 
	{
		long num = 0;
		int b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') 
		{
			minus = true;
			b = readByte();
		}
		
		while (true) 
		{
			if (b >= '0' && b <= '9') 
			{
				num = num * 10 + (b - '0');
			}
			else 
			{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private boolean oj = System.getProperty("ONLINE_JUDGE") != null;
	
	private void tr(Object... o) 
	{
		if (!oj)
			System.out.println(Arrays.deepToString(o));
	}
	
}