Brand New Game

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Consider the following game that is played on the field of the size of 1 x N cells. The cells are numbered from 1 to N. In the ith cell there are two positive integers written  A_{i} and B_{i}.
The game is as follows. Initially, the player stands at the fictive cell with the index 0 that is located right before all the N cells of the board. Then, he makes moves. Each move consists in moving by no more than by K cells forward. The goal of the game is to reach the fictive N+1th cell that is located right after all the N cells.
After the N+1th cell is reached, the player's penalty is calculated. The penalty equals to max(A_{x}) * max(B_{y}), where x and y are the indices of the cells that were visited in between (during the movement to the N+1th cell).
Please find the minimal possible penalty that can be reached in this game.
Input
The first line of input contains two single space separated integer numbers  N and K respectively.
Then, there are N lines, each containing a pair of signle space separated integers  A_{i} and B_{i} respectively.
Output
Output the minimal possible penalty on the first line.
Constraints
 1 ≤ K ≤ N
 1 ≤ N ≤ 100, 1 ≤ A_{i}, B_{i} ≤ 100  27 points.
 1 ≤ N ≤ 1000, 1 ≤ A_{i}, B_{i} ≤ 32000  20 points.
 1 ≤ N ≤ 5 * 10^{5}, 1 ≤ A_{i}, B_{i} ≤ 32000  53 points.
Example
Input: 5 3 1 5 2 4 3 3 4 2 5 1 Output: 9
Author:  xcwgf666 
Tester:  stzgd 
Editorial  http://discuss.codechef.com/problems/BNGAME 
Tags  easy ltime12 stl twopointers xcwgf666 
Date Added:  8052014 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 
Nice one! Thank you! :)