softeer lv2. 금고털이

softeer: https://softeer.ai/practice/info.do?idx=1&eid=395

문제

루팡은 배낭을 하나 메고 은행금고에 들어왔다. 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 들어있다. 배낭은 W ㎏까지 담을 수 있다.

각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가?

루팡은 전동톱을 가지고 있으며 귀금속은 톱으로 자르면 잘려진 부분의 무게만큼 가치를 가진다.

제약조건

1 ≤ N ≤ 106인 정수

1 ≤ W ≤ 104인 정수

1 ≤ Mi, Pi ≤ 104인 정수

입력형식

첫 번째 줄에 배낭의 무게 W와 귀금속의 종류 N이 주어진다. i + 1 (1 ≤ i ≤ N)번째 줄에는 i번째 금속의 무게 Mi와 무게당 가격 Pi가 주어진다.

출력형식

첫 번째 줄에 배낭에 담을 수 있는 가장 비싼 가격을 출력하라.

---

입력예제1

100 2 90 1 70 2

출력예제1

170

---

자바 코드

import java.util.*;
import java.io.*;


public class Main
{
    public static void main(String args[]) throws Exception
    {
        //Scanner sc = new Scanner(System.in);


        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer stBr = new StringTokenizer(br.readLine()," ");
        String[] tokens = new String[2];

        int stBrIndex = 0;
        while(stBr.hasMoreTokens()) {
            tokens[stBrIndex] = stBr.nextToken();
            stBrIndex++;
        }

        int bagWeight = Integer.parseInt(tokens[0]);
        int jKinds = Integer.parseInt(tokens[1]);

        int[][] jews = new int[jKinds][2];

        int highCost;
        for (int jew[] : jews) {
            StringTokenizer stBr2 = new StringTokenizer(br.readLine()," ");
            String[] tokens2 = new String[2];

            int stBrIndex2 = 0;
            while(stBr2.hasMoreTokens()) {
                tokens2[stBrIndex2] = stBr2.nextToken();
                stBrIndex2++;
            }            

            jew[1] = Integer.parseInt(tokens2[0]);
            jew[0] = Integer.parseInt(tokens2[1]);

        }

        //무게 당 값이 많이 나가는 보석부터 내림차순 정렬
        Arrays.sort(jews, (o1,o2)->(o2[0]-o1[0]));

        int inBag = 0;
        int totalPrice = 0;
        int prevInBag;
        for (int jew[] : jews) {
            //보석 담기
            inBag += jew[1];
            totalPrice += jew[1]*jew[0];

            //현재 보석을 담고 가방 무게가 넘칠 경우 보석 빼고 남은 무게 만큼 보석 커팅 후 다시 보석 담기
            if (inBag > bagWeight) {
                inBag -= jew[1]; //보석 빼기
                totalPrice -= jew[1]*jew[0]; //가격 빼기     

                int space = bagWeight - inBag;
                inBag += space;
                totalPrice += space*jew[0];
            } 

        }

        System.out.println(totalPrice);
    }
}

ps. scanner로 값을 받으니 시간초과되어 실패했다. BufferedReader를 쓰는 습관을 길러야 할 듯.