시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 512 MB350715724.051%

문제

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

백남이는 여행에 필요하다고 생각하는 필수품 $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$까지이다.

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

출력

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

예제 입력 1

5 3
6 10
10 15
5 10
7 13
4 9
20
21
22

예제 출력 1

3

1번 배낭이 담을 수 있는 무게는 20이고, 담을 수 있는 최대 가치는 34이므로 효율성은 1.7이다.

2번 배낭이 담을 수 있는 무게는 21이고, 담을 수 있는 최대 가치는 37이므로 효율성은 약 1.76이다.

3번 배낭이 담을 수 있는 무게는 22이고, 담을 수 있는 최대 가치는 42이므로 효율성은 약 1.9이다.

따라서 백남이가 선택해야하는 배낭은 3번 배낭이다.

출처

University > 충남대학교 > 제5회 생각하는 프로그래밍 대회  G번