해병대 전우, Soldier Han이 있습니다. 용감한 Han은 지구를 침략한 외계인에 맞서 싸우는 중입니다. Han의 앞에 소위 울트라리스크라고 불리는 거대한 외계 생명체가 한 마리 있습니다. Han은 그의 총 한 자루로 울트라리스크를 잡을 것입니다.
Han이 가지고 있는 총의 기본 공격력은 1입니다. 1초에 Han번씩 공격할 수 있습니다. 그런데, Han은 공격하는 것 대신에, 일정 시간동안 연구를 해서 자신의 총을 업그레이드 할 수 있습니다. 업그레이드를 하면 기본 공격력이 증가합니다. 업그레이드는 1단계, 2단계, 3단계, ... , n단계 업그레이드까지 있는데, i단계 업그레이드를 하면 기본 공격력이 +i가 됩니다. 업그레이드를 위한 연구 중에는 울트라리스크를 공격할 수 없습니다. 각 단계별 업그레이드에는 연구 횟수 제한이 있습니다. 예를 들어, 3단계 업그레이드의 연구 횟수 제한이 5번이라면, 3단계 업그레이드는 최대 5번만 가능합니다. Han이 울트라리스크를 잡을 수 있는 최소 시간과, 가장 빨리 잡을 수 있도록 하는 업그레이드 순서를 구해주세요.
입력으로 울트라리스크의 초기 체력 K (K는 1,000,000,000이하의 자연수)와 n단계 (n은 1,000,000이하의 자연수) 업그레이드까지의 정보를 담은 배열 A, B가 주어집니다. A[i]에는 i단계 업그레이드에 필요한 연구 시간이 들어있습니다. B[i]에는 i단계 업그레이드의 연구 횟수 제한이 들어있습니다. 연구 시간은 1,000,000,000 이하의 자연수입니다 (제한시간 1초).
*영감을 받은 곳: 비밀
*회고: 이런 류의 게임 자주 해봤다.
