컨테이너를 어떻게 채울까?

공장에서 만든 제품은 원기둥 모양의 상자에 담아 포장한다. 모든 상자의 밑면은 서로 같다. 상자의 높이는 항상 2의 거듭제곱이다. 즉 어떤 정수 $i = 0, 1, 2, \ldots$ 에 대해 높이가 $2^i$ 이다. 이 지수 $i$ 를 상자의 크기라고 부른다. 모든 상자에는 같은 종류의 물건이 들어 있지만 그 가치는 서로 다를 수 있다. 먼저 생산된 물건일수록 더 저렴하며, 창고에서는 가장 오래된(가장 저렴한) 물건부터 내보내려고 한다.

창고의 물건은 컨테이너에 실어 운반한다. 컨테이너도 원기둥 모양이고, 지름이 상자보다 약간 커서 상자를 쉽게 넣을 수 있다. 컨테이너의 높이 역시 2의 거듭제곱이며, 그 지수를 컨테이너의 크기라고 부른다. 안전한 운반을 위해 컨테이너는 상자로 빈틈없이 채워야 한다. 즉, 한 컨테이너에 담은 상자들의 높이 합이 그 컨테이너의 높이와 정확히 같아야 한다. 각 상자는 최대 하나의 컨테이너에만 넣을 수 있으며, 창고의 모든 상자를 반드시 사용할 필요는 없다.

창고로 여러 개의 컨테이너가 들어왔다. 창고에 있는 상자들로 주어진 모든 컨테이너를 빈틈없이 채울 수 있는지 판단하라. 채울 수 있다면, 그렇게 채울 때 컨테이너에 담기는 물건들의 가치 합이 최소가 되도록 했을 때의 그 최솟값을 구하라.

다음을 수행하는 프로그램을 작성하라.

• 표준 입력에서 창고에 있는 상자들의 정보(크기와 가치)와 들어온 컨테이너들의 정보(크기별 개수)를 읽는다.
• 창고의 상자들로 모든 컨테이너를 빈틈없이 채울 수 있는지 확인하고, 채울 수 있다면 채워지는 물건들의 가치 합의 최솟값을 계산한다.
• 그 결과를 표준 출력에 출력한다.

첫째 줄에 창고에 있는 상자의 개수를 나타내는 정수 $n$ 이 주어진다 ($1 \le n \le 10000$). 이어지는 $n$ 개의 줄에는 각각 공백으로 구분된 두 개의 음이 아닌 정수가 주어지며, 이는 상자 하나를 나타낸다. 첫 번째 정수는 그 상자의 크기이고, 두 번째 정수는 그 상자에 담긴 물건의 가치이다. 크기는 1,000 이하이고, 가치는 10,000 이하이다.

그 다음 줄에는 창고로 들어온 컨테이너의 서로 다른 크기가 몇 종류인지를 나타내는 양의 정수 $q$ 가 주어진다. 이어지는 $q$ 개의 줄에는 각각 공백으로 구분된 두 개의 양의 정수가 주어진다. 첫 번째 정수는 컨테이너의 크기이고, 두 번째 정수는 그 크기를 가진 컨테이너의 개수이다. 컨테이너의 총 개수는 최대 5,000 개이며, 컨테이너의 크기는 1,000 이하이다.

표준 출력의 첫째 줄이자 유일한 줄에 다음을 출력한다.

• 주어진 컨테이너들을 창고의 상자들로 빈틈없이 채우는 것이 불가능하면, NIE 라는 단어 하나만 출력한다.
• 채우는 것이 가능하면, 모든 컨테이너를 빈틈없이 채울 때 담기는 물건들의 가치 합의 최솟값을 정수 하나로 출력한다.