Nearest Station
시간 제한1초메모리 제한512 MB
p*a_k + q*b_k만큼 이동하는 티켓 n장 중 일부를 골라 합이 m에 가장 가깝게 만든 뒤, 남은 최소 도보 칸수를 출력한다.
문제
うさぎがある電車のチケットをn 枚持っている. チケットにはそれぞれ0 からn − 1 までの番号がついていて, k 番のチケットを使うと, p⋅ak + q⋅bk 駅進むことができる.
うさぎは今いる駅からm 駅進んだ駅にあるニンジン食べ放題の店に行きたいが, なるべく歩く距離を短くしたい. 駅は等間隔に並んでいる. チケットを電車の上り線で進むことのみに用いるとき, うさぎは最小何駅分の徒歩で店に着けるか.
입력
1 ≤ n, m, a, b, p, q ≤ 1 000 000 000 000 (整数)
출력
うさぎは最小何駅分の徒歩で店に着けるか, その数を一行に出力せよ.