# Poj Solution 3115

```http://poj.org/problem?id=3115

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

int main( ) {
__int64 m[4][2], *ans = m[0], *temp = m[1], *id = m[2], *idt = m[3], s1, s2,
mem[2][20], *res = mem[0], *rest = mem[1];
int en[20], ti[20];
int f, p, e, a, i, j;

while( 1 ) {
scanf( "%d%d%d%d", &f, &p, &e, &a );
e *= a;
if( f == 0 && p == 0 && e == 0 && a == 0 ) break;

ans[0] = 0;
ans[1] = 50000000000;
id[0] = 0;
id[1] = 1;

for( j=0; j<f; j++ )
res[j] = 50000000000;

for( i=0; i<p; i++ ) {
for( j=0; j<f; j++ ) {
scanf( "%d%d", en+j, ti+j );
en[j] *= ti[j];
}

temp[0] = 50000000000;
temp[1] = 50000000000;

for( j=0; j<f; j++ ) {
s1 = ans[0] + en[j] + e*(j!=id[0]);
s2 = ans[1] + en[j] + e*(j!=id[1]);
rest[j] = res[j] + en[j];

if( s1 < rest[j] ) rest[j] = s1;
if( s2 < rest[j] ) rest[j] = s2;

if( rest[j] < temp[0] ) {
temp[1] = temp[0], idt[1] = idt[0];
temp[0] = rest[j], idt[0] = j;
}
else if( rest[j] < temp[1] )
temp[1] = rest[j], idt[1] = j;
}

swap( temp, ans );
swap( id, idt );
swap( rest, res );
}

printf( "%I64dn", ans[0] );
}
return 0;
}

```
This entry was posted in poj. Bookmark the permalink.