# -*- coding: utf-8 -*-
import math
import random
import copy
 
# グローバル変数
MAXVALUE = 100
N = 30
WEIGHTLIMIT = N * MAXVALUE / 4
POOLSIZE = 30
LASTG = 50
MRATE = 0.01
SEED = 32767
parcel = [[0 for i in range(2)] for j in range(N)]
 
# 必要な関数のみ定義
def rndn(n):
    return random.randint(0, n - 1)
 
def initparcel():
    i = 0
    while i < N:
        try:
            line = input()
            if not line: break
        except EOFError:
            break
        parts = line.split()
        if len(parts) >= 2:
            parcel[i] = [int(parts[0]), int(parts[1])]
            i += 1
 
def evalfit(g):
    value = 0
    weight = 0
    for pos in range(N):
        weight += parcel[pos][0] * g[pos]
        value += parcel[pos][1] * g[pos]
    if weight >= WEIGHTLIMIT:
        value = 0
    return value
 
def selectp(roulette, totalfitness):
    acc = 0
    ball = rndn(totalfitness)
    for i in range(POOLSIZE):
        acc += roulette[i]
        if acc > ball: break
    return i
 
def crossing(m, p, c1, c2):
    cp = rndn(N)
    for j in range(cp):
        c1[j] = m[j]
        c2[j] = p[j]
    for j in range(cp, N):
        c2[j] = m[j]
        c1[j] = p[j]
 
def mutation(ngpool):
    for i in range(POOLSIZE * 2):
        for j in range(N):
            if random.random() < MRATE:
                ngpool[i][j] = 1 if ngpool[i][j] == 0 else 0
 
def mating(pool, ngpool):
    roulette = [evalfit(pool[i]) for i in range(POOLSIZE)]
    totalfitness = sum(roulette)
    for i in range(POOLSIZE):
        while True:
            mama = selectp(roulette, totalfitness)
            papa = selectp(roulette, totalfitness)
            if mama != papa: break
        crossing(pool[mama], pool[papa], ngpool[i * 2], ngpool[i * 2 + 1])
 
def selectng(ngpool, pool):
    roulette = [evalfit(ngpool[i]) for i in range(POOLSIZE * 2)]
    totalfitness = sum(roulette)
    for i in range(POOLSIZE):
        ball = rndn(totalfitness)
        acc = 0
        for c in range(POOLSIZE * 2):
            acc += roulette[c]
            if acc > ball: break
        pool[i] = copy.deepcopy(ngpool[c])
 
# 結果出力（グラフ用データのみ）
def print_graph_data(generation, pool):
    totalfitness = 0
    bestfit = 0
    elite = 0
    for i in range(POOLSIZE):
        fitness = evalfit(pool[i])
        if fitness > bestfit:
            bestfit = fitness
            elite = i
        totalfitness += fitness
    # 世代, エリート番号, 最良値, 平均値
    print(generation, elite, bestfit, totalfitness / POOLSIZE)
 
# メイン実行部
random.seed(SEED)
pool = [[rndn(2) for i in range(N)] for j in range(POOLSIZE)]
ngpool = [[0 for i in range(N)] for j in range(POOLSIZE * 2)]
initparcel()
 
# 0世代目のデータ出力
print_graph_data(0, pool)
 
for generation in range(1, LASTG):
    mating(pool, ngpool)
    mutation(ngpool)
    selectng(ngpool, pool)
    print_graph_data(generation, pool)

IyAtKi0gY29kaW5nOiB1dGYtOCAtKi0KaW1wb3J0IG1hdGgKaW1wb3J0IHJhbmRvbQppbXBvcnQgY29weQoKIyDjgrDjg63jg7zjg5Djg6vlpInmlbAKTUFYVkFMVUUgPSAxMDAKTiA9IDMwCldFSUdIVExJTUlUID0gTiAqIE1BWFZBTFVFIC8gNApQT09MU0laRSA9IDMwCkxBU1RHID0gNTAKTVJBVEUgPSAwLjAxClNFRUQgPSAzMjc2NwpwYXJjZWwgPSBbWzAgZm9yIGkgaW4gcmFuZ2UoMildIGZvciBqIGluIHJhbmdlKE4pXQoKIyDlv4XopoHjgarplqLmlbDjga7jgb/lrprnvqkKZGVmIHJuZG4obik6CiAgICByZXR1cm4gcmFuZG9tLnJhbmRpbnQoMCwgbiAtIDEpCgpkZWYgaW5pdHBhcmNlbCgpOgogICAgaSA9IDAKICAgIHdoaWxlIGkgPCBOOgogICAgICAgIHRyeToKICAgICAgICAgICAgbGluZSA9IGlucHV0KCkKICAgICAgICAgICAgaWYgbm90IGxpbmU6IGJyZWFrCiAgICAgICAgZXhjZXB0IEVPRkVycm9yOgogICAgICAgICAgICBicmVhawogICAgICAgIHBhcnRzID0gbGluZS5zcGxpdCgpCiAgICAgICAgaWYgbGVuKHBhcnRzKSA+PSAyOgogICAgICAgICAgICBwYXJjZWxbaV0gPSBbaW50KHBhcnRzWzBdKSwgaW50KHBhcnRzWzFdKV0KICAgICAgICAgICAgaSArPSAxCgpkZWYgZXZhbGZpdChnKToKICAgIHZhbHVlID0gMAogICAgd2VpZ2h0ID0gMAogICAgZm9yIHBvcyBpbiByYW5nZShOKToKICAgICAgICB3ZWlnaHQgKz0gcGFyY2VsW3Bvc11bMF0gKiBnW3Bvc10KICAgICAgICB2YWx1ZSArPSBwYXJjZWxbcG9zXVsxXSAqIGdbcG9zXQogICAgaWYgd2VpZ2h0ID49IFdFSUdIVExJTUlUOgogICAgICAgIHZhbHVlID0gMAogICAgcmV0dXJuIHZhbHVlCgpkZWYgc2VsZWN0cChyb3VsZXR0ZSwgdG90YWxmaXRuZXNzKToKICAgIGFjYyA9IDAKICAgIGJhbGwgPSBybmRuKHRvdGFsZml0bmVzcykKICAgIGZvciBpIGluIHJhbmdlKFBPT0xTSVpFKToKICAgICAgICBhY2MgKz0gcm91bGV0dGVbaV0KICAgICAgICBpZiBhY2MgPiBiYWxsOiBicmVhawogICAgcmV0dXJuIGkKCmRlZiBjcm9zc2luZyhtLCBwLCBjMSwgYzIpOgogICAgY3AgPSBybmRuKE4pCiAgICBmb3IgaiBpbiByYW5nZShjcCk6CiAgICAgICAgYzFbal0gPSBtW2pdCiAgICAgICAgYzJbal0gPSBwW2pdCiAgICBmb3IgaiBpbiByYW5nZShjcCwgTik6CiAgICAgICAgYzJbal0gPSBtW2pdCiAgICAgICAgYzFbal0gPSBwW2pdCgpkZWYgbXV0YXRpb24obmdwb29sKToKICAgIGZvciBpIGluIHJhbmdlKFBPT0xTSVpFICogMik6CiAgICAgICAgZm9yIGogaW4gcmFuZ2UoTik6CiAgICAgICAgICAgIGlmIHJhbmRvbS5yYW5kb20oKSA8IE1SQVRFOgogICAgICAgICAgICAgICAgbmdwb29sW2ldW2pdID0gMSBpZiBuZ3Bvb2xbaV1bal0gPT0gMCBlbHNlIDAKCmRlZiBtYXRpbmcocG9vbCwgbmdwb29sKToKICAgIHJvdWxldHRlID0gW2V2YWxmaXQocG9vbFtpXSkgZm9yIGkgaW4gcmFuZ2UoUE9PTFNJWkUpXQogICAgdG90YWxmaXRuZXNzID0gc3VtKHJvdWxldHRlKQogICAgZm9yIGkgaW4gcmFuZ2UoUE9PTFNJWkUpOgogICAgICAgIHdoaWxlIFRydWU6CiAgICAgICAgICAgIG1hbWEgPSBzZWxlY3RwKHJvdWxldHRlLCB0b3RhbGZpdG5lc3MpCiAgICAgICAgICAgIHBhcGEgPSBzZWxlY3RwKHJvdWxldHRlLCB0b3RhbGZpdG5lc3MpCiAgICAgICAgICAgIGlmIG1hbWEgIT0gcGFwYTogYnJlYWsKICAgICAgICBjcm9zc2luZyhwb29sW21hbWFdLCBwb29sW3BhcGFdLCBuZ3Bvb2xbaSAqIDJdLCBuZ3Bvb2xbaSAqIDIgKyAxXSkKCmRlZiBzZWxlY3RuZyhuZ3Bvb2wsIHBvb2wpOgogICAgcm91bGV0dGUgPSBbZXZhbGZpdChuZ3Bvb2xbaV0pIGZvciBpIGluIHJhbmdlKFBPT0xTSVpFICogMildCiAgICB0b3RhbGZpdG5lc3MgPSBzdW0ocm91bGV0dGUpCiAgICBmb3IgaSBpbiByYW5nZShQT09MU0laRSk6CiAgICAgICAgYmFsbCA9IHJuZG4odG90YWxmaXRuZXNzKQogICAgICAgIGFjYyA9IDAKICAgICAgICBmb3IgYyBpbiByYW5nZShQT09MU0laRSAqIDIpOgogICAgICAgICAgICBhY2MgKz0gcm91bGV0dGVbY10KICAgICAgICAgICAgaWYgYWNjID4gYmFsbDogYnJlYWsKICAgICAgICBwb29sW2ldID0gY29weS5kZWVwY29weShuZ3Bvb2xbY10pCgojIOe1kOaenOWHuuWKm++8iOOCsOODqeODleeUqOODh+ODvOOCv+OBruOBv++8iQpkZWYgcHJpbnRfZ3JhcGhfZGF0YShnZW5lcmF0aW9uLCBwb29sKToKICAgIHRvdGFsZml0bmVzcyA9IDAKICAgIGJlc3RmaXQgPSAwCiAgICBlbGl0ZSA9IDAKICAgIGZvciBpIGluIHJhbmdlKFBPT0xTSVpFKToKICAgICAgICBmaXRuZXNzID0gZXZhbGZpdChwb29sW2ldKQogICAgICAgIGlmIGZpdG5lc3MgPiBiZXN0Zml0OgogICAgICAgICAgICBiZXN0Zml0ID0gZml0bmVzcwogICAgICAgICAgICBlbGl0ZSA9IGkKICAgICAgICB0b3RhbGZpdG5lc3MgKz0gZml0bmVzcwogICAgIyDkuJbku6MsIOOCqOODquODvOODiOeVquWPtywg5pyA6Imv5YCkLCDlubPlnYflgKQKICAgIHByaW50KGdlbmVyYXRpb24sIGVsaXRlLCBiZXN0Zml0LCB0b3RhbGZpdG5lc3MgLyBQT09MU0laRSkKCiMg44Oh44Kk44Oz5a6f6KGM6YOoCnJhbmRvbS5zZWVkKFNFRUQpCnBvb2wgPSBbW3JuZG4oMikgZm9yIGkgaW4gcmFuZ2UoTildIGZvciBqIGluIHJhbmdlKFBPT0xTSVpFKV0Kbmdwb29sID0gW1swIGZvciBpIGluIHJhbmdlKE4pXSBmb3IgaiBpbiByYW5nZShQT09MU0laRSAqIDIpXQppbml0cGFyY2VsKCkKCiMgMOS4luS7o+ebruOBruODh+ODvOOCv+WHuuWKmwpwcmludF9ncmFwaF9kYXRhKDAsIHBvb2wpCgpmb3IgZ2VuZXJhdGlvbiBpbiByYW5nZSgxLCBMQVNURyk6CiAgICBtYXRpbmcocG9vbCwgbmdwb29sKQogICAgbXV0YXRpb24obmdwb29sKQogICAgc2VsZWN0bmcobmdwb29sLCBwb29sKQogICAgcHJpbnRfZ3JhcGhfZGF0YShnZW5lcmF0aW9uLCBwb29sKQ==

NjUgMjcKMzkgODIKOSA4NQo3MiA3MQo4NyA5MQo5MSAyOAozNCA5Mgo1OCA3OQozIDI3CjEyIDgyCjkyIDE1CjM5IDQ5CjgzIDU0Cjc2IDQzCjYgMjYKNzcgMgo2OCA2CjI0IDYwCjYwIDQ3CjYgNDAKOTEgNTgKNDQgNjgKNTAgMzMKOTEgOTIKNTcgNjIKOTcgNDkKOTYgNjgKMzkgNzcKODkgNgoyNCA5Nw==

65 27
39 82
9 85
72 71
87 91
91 28
34 92
58 79
3 27
12 82
92 15
39 49
83 54
76 43
6 26
77 2
68 6
24 60
60 47
6 40
91 58
44 68
50 33
91 92
57 62
97 49
96 68
39 77
89 6
24 97