23061번 - 백남이의 여행 준비

방학을 맞은 귀여운 백남이는 여행을 떠날 준비를 하고 있다.

백남이는 여행에 필요하다고 생각하는 필수품 $N$개를 가지고 있다. 각 물건은 무게 $W$와 가치 $V$를 가진다. 그리고 백남이는 물건을 담을 가방 $M$개를 가지고 있는데, 각각의 가방은 최대 $K_i$만큼의 무게를 견딜 수 있다.

MBTI가 J(판단형)인 백남이는 효율성을 중요하게 여기기 때문에, 가장 효율적으로 짐을 싸지 않으면 여행을 출발할 수 없다. 백남이가 정의한 효율성은 (가방에 담긴 물건의 가치의 합) / (가방이 견딜 수 있는 최대 무게)이다.

가방과 물건의 정보가 주어졌을 때, 가장 효율적으로 짐을 싸기 위해 필요한 가방이 무엇인지 알아내자. 가방은 한 개만 선택할 수 있으며, 최적의 가방이 여러 가지라면 그중 가장 작은 번호를 출력한다.

첫 줄에 물품의 수 $N(1 ≤ N ≤ 100)$과 가방의 수 $M(1 ≤ M ≤ 100)$가 주어진다.

두 번째 줄부터 $N$ 개의 줄에 거쳐 각 물건의 무게 $W(1 ≤ W ≤ 100,000)$와 해당 물건의 가치 $V(0 ≤ V ≤ 1,000)$가 주어진다.

그 후에는 $M$ 개의 줄에 거쳐 가방이 버틸 수 있는 최대 무게 $K_i (1 ≤ K_i ≤ 1,000,000)$가 주어진다. 가방의 번호는 $1$부터 $M$까지이다.

입력으로 주어지는 모든 수는 정수이다.

한 줄에 가장 효율적으로 짐을 싸기 위해 필요한 가방의 번호를 출력한다.