你正步入你的大學生涯的第一年，作為一個新生，有很多事情需要好好計劃一下。其中一項就是你每天晚上的晚餐。一個學期共有N餐晚餐。

你住在大學宿舍，大學規定一年級生必需留在大學餐廳用餐。然而，大學內有數間(M間)餐廳可選擇，而這些餐廳為了爭取客人，均提供一些優惠。出奇地，這些餐廳的優惠型式都是相同的，只是一些詳細內容不同而已。

優惠的規則如下：

• 餐廳在學期的第一天就會公佈該學期內每晚的晚餐內容及價錢
• 每個學生只能購買一間餐廳的餐卡，一旦購買了一間餐廳的餐卡，整個學期都需要在該餐廳用餐
• 每個學生每晚用餐時，他可以選擇交全費或享用節扣價(R%)，若學生選擇交全費的話，他就可以在他的餐卡上盖一個印章。但若享用節扣價的話，則不可以蓋印。
• 當一個學生的餐卡上印了K個或以上的印時，他可以選擇在進入餐廳時，用他的印有足夠印章的餐卡來換取免費享用當晚的晚餐，這時，餐廳就會收了他的那張餐卡，同時發給他一張全新(沒有任何印章)的餐卡。之後這位學生可以繼續用他的全新餐卡重新開始儲印章來換取其後免費晚餐。

每間餐廳都使用同樣的方法來提供優惠，所不同的是晚餐的內容，每餐的價錢，及相關的節扣率R及要求的印章數目K。

當然，晚餐的內容是個很重要的因素，但費用的多少也是一個不得不考慮的因素。於是你想找出利用餐廳提供的優惠方案，要在整學期在某一間餐廳所需要付的最少費用會是多少？因為你在某一間餐廳選擇何時付全費，享用節扣價或享用免費大餐會有不同的結果。