Earliest Software Delivery

A software company must develop and deliver two software products simultaneously. Each software is divided into m modules. There are n technicians available. For each technician, the time required to complete any module of the same software is constant and is known, but the times for the two different softwares are different. A technician can only work on one module at any given time, and each module must be completed entirely by one technician (i.e. no collaboration on a single module). After finishing a module, a technician may immediately start any remaining module, regardless of which software it belongs to.

Given the number of modules per software and, for each technician, the number of days they take to complete one module from Software 1 and Software 2 respectively, determine the minimum number of days needed so that both softwares are completely finished.

The problem can be formulated as follows. For each technician i (1 ≤ i ≤ n) with two processing times \( p_i \) (Software 1) and \( q_i \) (Software 2), you must decide how many modules \( x_i \) (for Software 1) and \( y_i \) (for Software 2) they will complete such that

[ \begin{aligned} p_i,x_i + q_i,y_i &\le T, \quad \forall i = 1,2,\dots,n, \ \sum_{i=1}^{n} x_i &\ge m, \ \sum_{i=1}^{n} y_i &\ge m. \end{aligned} ]

Find the minimum \( T \) for which there exist nonnegative integers \( x_i, y_i \) satisfying the conditions.

inputFormat

The first line contains two integers \( n \) and \( m \) (1 ≤ n, m ≤ small constraints) separated by a space.

Then follow \( n \) lines. The i-th line contains two integers \( p_i \) and \( q_i \) (each positive) separated by a space, which represent the number of days technician i needs to complete a module of Software 1 and Software 2 respectively.

outputFormat

Output a single integer \( T \), the minimum number of days required to complete both software products.

sample

2 1
10 1
1 10

1