Bob came to a cash & carry store, put n items into his trolley, and went to the checkout counter to pay. Each item is described by its price ci and time ti in seconds that a checkout assistant spends on this item. While the checkout assistant is occupied with some item, Bob can steal some other items from his trolley. To steal one item Bob needs exactly 1 second. What is the minimum amount of money that Bob will have to pay to the checkout assistant? Remember, please, that it is Bob, who determines the order of items for the checkout assistant.

Input

The first input line contains number n (1 ≤ n ≤ 2000). In each of the following n lines each item is described by a pair of numbers ti, ci (0 ≤ ti ≤ 2000, 1 ≤ ci ≤ 109). If ti is 0, Bob won't be able to steal anything, while the checkout assistant is occupied with item i.

Output

Output one number — answer to the problem: what is the minimum amount of money that Bob will have to pay.

Examples

Input

4
2 10
0 20
1 5
1 3


Output

8


Input

3
0 1
0 10
0 100


Output

111
import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
 
public class Main1 {
	static PrintWriter out = new PrintWriter(System.out, true);
 
	static final int OFFSET = 2000;
	static int n, a[][]; // 0 time , 1 cost
	static boolean[][] v;
	static long memo[][];
	static final long LINF = (long) 1e15;
 
	static long solve(int indx, int time) {
		if (indx >= n) {
			if (time >= OFFSET) {
				return 0;
			}
			return LINF;
		}
 
		if (v[indx][time]) {
			return memo[indx][time];
		}
		v[indx][time] = true;
 
		long pay = a[indx][1] + solve(indx + 1, Math.min(time + a[indx][0], 2 * OFFSET));
		long steal = solve(indx + 1, time - 1);
 
		return memo[indx][time] = Math.min(pay, steal);
 
	}
 
	public static void main(String[] args) throws IOException {
		Reader input = new Reader();
		n = input.nextInt();
		a = new int[n][2];
 
		for (int i = 0; i < n; i++) {
			a[i][0] = input.nextInt();
			a[i][1] = input.nextInt();
		}
 
		memo = new long[n + 1][2 * OFFSET + 10];
		v = new boolean[n + 1][2 * OFFSET + 10];
 
		long ans = solve(0, OFFSET);
		out.println(ans);
		out.flush();
 
	}
 
	static class FastReader {
		BufferedReader br;
		StringTokenizer st;
 
		public FastReader() {
			// try {
			// br = new BufferedReader(new FileReader(new File("overcode.in")));
			// } catch (FileNotFoundException e) {
			// e.printStackTrace();
			// }
			br = new BufferedReader(new InputStreamReader(System.in));
		}
 
		String next() throws IOException {
			while (st == null || !st.hasMoreElements()) { st = new StringTokenizer(br.readLine()); }
			return st.nextToken();
		}
 
		int nextInt() throws NumberFormatException, IOException { return Integer.parseInt(next()); }
 
		long nextLong() throws NumberFormatException, IOException { return Long.parseLong(next()); }
 
		double nextDouble() throws NumberFormatException, IOException { return Double.parseDouble(next()); }
 
		String nextLine() throws IOException {
			String str = "";
			str = br.readLine();
			return str;
		}
 
		boolean hasNext() throws IOException { return br.ready(); }
	}
 
	static class con {
		static int IINF = (int) 1e9;
		static int _IINF = (int) -1e9;
		static long LINF = (long) 1e15;
		static long _LINF = (long) -1e15;
		static double EPS = 1e-9;
	}
 
	static class Triple implements Comparable<Triple> {
		int x;
		int y;
 
		int z;
 
		Triple(int x, int y, int z) {
			this.x = x;
			this.y = y;
			this.z = z;
		}
 
		@Override
		public int compareTo(Triple o) {
			if (x == o.x && y == o.y)
				return z - o.z;
			if (x == o.x)
				return y - o.y;
			return x - o.x;
		}
 
		@Override
		public String toString() { return "(" + x + ", " + y + ", " + z + ")"; }
	}
 
	static class Pair implements Comparable<Pair> {
		int x;
		int y;
 
		Pair(int x, int y) {
			this.x = x;
			this.y = y;
 
		}
 
		@Override
		public int compareTo(Pair o) {
			if (x == o.x)
				return y - o.y;
			return x - o.x;
		}
 
		@Override
		public String toString() {
 
			return "(" + x + ", " + y + ")";
		}
 
	}
 
	static void shuffle(int[] a) {
		for (int i = 0; i < a.length; i++) {
			int r = i + (int) (Math.random() * (a.length - i));
			int tmp = a[r];
			a[r] = a[i];
			a[i] = tmp;
		}
	}
 
	static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
 
	static class DSU {
 
		int[] p, rank, setSize;
		int numSets;
 
		DSU(int n) {
			p = new int[n];
			rank = new int[n];
			setSize = new int[n];
			numSets = n;
 
			for (int i = 0; i < n; i++) {
				p[i] = i;
				setSize[i] = 1;
			}
 
		}
 
		int findSet(int n) { return p[n] = p[n] == n ? n : findSet(p[n]); }
 
		boolean isSameSet(int n, int m) { return findSet(n) == findSet(m); }
 
		void mergeSet(int n, int m) {
 
			if (!isSameSet(n, m)) {
				numSets--;
				int p1 = findSet(n);
				int p2 = findSet(m);
 
				if (rank[p1] > rank[p2]) {
					p[p2] = p1;
					setSize[p1] += setSize[p2];
				} else {
					p[p1] = p2;
					setSize[p2] += setSize[p1];
					if (rank[p1] == rank[p2])
						rank[p1]++;
				}
			}
 
		}
 
		int size() { return numSets; }
 
		int setSize(int n) { return setSize[findSet(n)]; }
 
	}
 
	static class Reader {
		final private int BUFFER_SIZE = 1 << 16;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer, bytesRead;
 
		public Reader() {
			din = new DataInputStream(System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}
 
		public Reader(String file_name) throws IOException {
			din = new DataInputStream(new FileInputStream(file_name));
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}
 
		public String readLine() throws IOException {
			byte[] buf = new byte[1024];
			int cnt = 0, c;
			while ((c = read()) != -1) {
				if (c == '\n')
					break;
				buf[cnt++] = (byte) c;
			}
			return new String(buf, 0, cnt);
		}
 
		public int nextInt() throws IOException {
			int ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do { ret = ret * 10 + c - '0'; } while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}
 
		public long nextLong() throws IOException {
			long ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do { ret = ret * 10 + c - '0'; } while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}
 
		public double nextDouble() throws IOException {
			double ret = 0, div = 1;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do { ret = ret * 10 + c - '0'; } while ((c = read()) >= '0' && c <= '9');
			if (c == '.')
				while ((c = read()) >= '0' && c <= '9')
					ret += (c - '0') / (div *= 10);
			if (neg)
				return -ret;
			return ret;
		}
 
		private void fillBuffer() throws IOException {
			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1)
				buffer[0] = -1;
		}
 
		private byte read() throws IOException {
			if (bufferPointer == bytesRead)
				fillBuffer();
			return buffer[bufferPointer++];
		}
 
		public void close() throws IOException {
			if (din == null)
				return;
			din.close();
		}
	}
}