adt = [
    ['北海道', 5248552, 83424.39], ['青森県', 1246138, 9645.64],
    ['岩手県', 1226430, 15275.01], ['宮城県', 2303160, 7282.29],
    ['秋田県', 965968, 11637.52], ['山形県', 1077057, 9323.15],
    ['福島県', 1847950, 13783.9], ['茨城県', 2868041, 6097.39],
    ['栃木県', 1942312, 6408.09], ['群馬県', 1937626, 6362.28],
    ['埼玉県', 7337330, 3797.75], ['千葉県', 6279026, 5157.6],
    ['東京都', 13942856, 2194.07], ['神奈川県', 9200166, 2416.3],
    ['新潟県', 2222004, 12584.24], ['富山県', 1042998, 4247.59],
    ['石川県', 1137181, 4186.05], ['福井県', 767742, 4190.52],
    ['山梨県', 812056, 4465.27], ['長野県', 2049023, 13561.56],
    ['岐阜県', 1988931, 10621.29], ['静岡県', 3639226, 7777.35],
    ['愛知県', 7552873, 5173.06], ['三重県', 1779770, 5774.45],
    ['滋賀県', 1413959, 4017.38], ['京都府', 2583140, 4612.2],
    ['大阪府', 8823453, 1905.29], ['兵庫県', 5463609, 8400.94],
    ['奈良県', 1331330, 3690.94], ['和歌山県', 923721, 4724.65],
    ['鳥取県', 555663, 3507.14], ['島根県', 673891, 6708.27],
    ['岡山県', 1891346, 7114.33], ['広島県', 2807987, 8479.64],
    ['山口県', 1355495, 6112.53], ['徳島県', 728633, 4146.75],
    ['香川県', 956069, 1876.79], ['愛媛県', 1338811, 5676.16],
    ['高知県', 697674, 7103.64], ['福岡県', 5110113, 4986.51],
    ['佐賀県', 814211, 2440.7], ['長崎県', 1325205, 4131.0],
    ['熊本県', 1746740, 7409.45], ['大分県', 1134431, 6340.76],
    ['宮崎県', 1072077, 7735.33], ['鹿児島県', 1599984, 9187.08],
    ['沖縄県', 1454184, 2281.0]
]

def ck(mid, cnt):
    wdt = []
    for z1,z2,z3 in adt:
        wdt.append(z2 - z3 * mid)
    wdt.sort(reverse = True)
    return sum(wdt[:cnt]) >= 0

def disp(mid, cnt):
    wdt = []
    for ix, z in enumerate(adt):
        wdt.append([z[1] - z[2] * mid, ix, z[1],z[2]])
    wdt.sort(reverse = True)
    smp, sma, ksi = 0, 0, 0
    for q in wdt[:cnt]:
        ksi |= 1<<q[1]
        smp += q[2]
        sma += q[3]
    print(f"{smp / sma:.6f}人/km2)\n [", end=" ")
    for i in range(47):
        if ksi>>i & 1: print(adt[i][0], end=" ")
    print("]")

def fnc(cnt):
    ok , ng = 0.0, 10000.0
    for q in range(100):
        mid = (ok + ng ) /2.0
        if ck(mid, cnt) : ok = mid
        else: ng = mid
    #print(ok)
    disp(ok, cnt)


fnc(20)

CgphZHQgPSBbCiAgICBbJ+WMl+a1t+mBkycsIDUyNDg1NTIsIDgzNDI0LjM5XSwgWyfpnZLmo67nnIwnLCAxMjQ2MTM4LCA5NjQ1LjY0XSwKICAgIFsn5bKp5omL55yMJywgMTIyNjQzMCwgMTUyNzUuMDFdLCBbJ+WuruWfjuecjCcsIDIzMDMxNjAsIDcyODIuMjldLAogICAgWyfnp4vnlLDnnIwnLCA5NjU5NjgsIDExNjM3LjUyXSwgWyflsbHlvaLnnIwnLCAxMDc3MDU3LCA5MzIzLjE1XSwKICAgIFsn56aP5bO255yMJywgMTg0Nzk1MCwgMTM3ODMuOV0sIFsn6Iyo5Z+O55yMJywgMjg2ODA0MSwgNjA5Ny4zOV0sCiAgICBbJ+agg+acqOecjCcsIDE5NDIzMTIsIDY0MDguMDldLCBbJ+e+pOmmrOecjCcsIDE5Mzc2MjYsIDYzNjIuMjhdLAogICAgWyfln7znjonnnIwnLCA3MzM3MzMwLCAzNzk3Ljc1XSwgWyfljYPokYnnnIwnLCA2Mjc5MDI2LCA1MTU3LjZdLAogICAgWyfmnbHkuqzpg70nLCAxMzk0Mjg1NiwgMjE5NC4wN10sIFsn56We5aWI5bed55yMJywgOTIwMDE2NiwgMjQxNi4zXSwKICAgIFsn5paw5r2f55yMJywgMjIyMjAwNCwgMTI1ODQuMjRdLCBbJ+WvjOWxseecjCcsIDEwNDI5OTgsIDQyNDcuNTldLAogICAgWyfnn7Plt53nnIwnLCAxMTM3MTgxLCA0MTg2LjA1XSwgWyfnpo/kupXnnIwnLCA3Njc3NDIsIDQxOTAuNTJdLAogICAgWyflsbHmoqjnnIwnLCA4MTIwNTYsIDQ0NjUuMjddLCBbJ+mVt+mHjuecjCcsIDIwNDkwMjMsIDEzNTYxLjU2XSwKICAgIFsn5bKQ6Zic55yMJywgMTk4ODkzMSwgMTA2MjEuMjldLCBbJ+mdmeWyoeecjCcsIDM2MzkyMjYsIDc3NzcuMzVdLAogICAgWyfmhJvnn6XnnIwnLCA3NTUyODczLCA1MTczLjA2XSwgWyfkuInph43nnIwnLCAxNzc5NzcwLCA1Nzc0LjQ1XSwKICAgIFsn5ruL6LOA55yMJywgMTQxMzk1OSwgNDAxNy4zOF0sIFsn5Lqs6YO95bqcJywgMjU4MzE0MCwgNDYxMi4yXSwKICAgIFsn5aSn6Ziq5bqcJywgODgyMzQ1MywgMTkwNS4yOV0sIFsn5YW15bqr55yMJywgNTQ2MzYwOSwgODQwMC45NF0sCiAgICBbJ+WliOiJr+ecjCcsIDEzMzEzMzAsIDM2OTAuOTRdLCBbJ+WSjOatjOWxseecjCcsIDkyMzcyMSwgNDcyNC42NV0sCiAgICBbJ+mzpeWPluecjCcsIDU1NTY2MywgMzUwNy4xNF0sIFsn5bO25qC555yMJywgNjczODkxLCA2NzA4LjI3XSwKICAgIFsn5bKh5bGx55yMJywgMTg5MTM0NiwgNzExNC4zM10sIFsn5bqD5bO255yMJywgMjgwNzk4NywgODQ3OS42NF0sCiAgICBbJ+WxseWPo+ecjCcsIDEzNTU0OTUsIDYxMTIuNTNdLCBbJ+W+s+WztuecjCcsIDcyODYzMywgNDE0Ni43NV0sCiAgICBbJ+mmmeW3neecjCcsIDk1NjA2OSwgMTg3Ni43OV0sIFsn5oSb5aqb55yMJywgMTMzODgxMSwgNTY3Ni4xNl0sCiAgICBbJ+mrmOefpeecjCcsIDY5NzY3NCwgNzEwMy42NF0sIFsn56aP5bKh55yMJywgNTExMDExMywgNDk4Ni41MV0sCiAgICBbJ+S9kOizgOecjCcsIDgxNDIxMSwgMjQ0MC43XSwgWyfplbfltI7nnIwnLCAxMzI1MjA1LCA0MTMxLjBdLAogICAgWyfnhormnKznnIwnLCAxNzQ2NzQwLCA3NDA5LjQ1XSwgWyflpKfliIbnnIwnLCAxMTM0NDMxLCA2MzQwLjc2XSwKICAgIFsn5a6u5bSO55yMJywgMTA3MjA3NywgNzczNS4zM10sIFsn6bm/5YWQ5bO255yMJywgMTU5OTk4NCwgOTE4Ny4wOF0sCiAgICBbJ+aylue4hOecjCcsIDE0NTQxODQsIDIyODEuMF0KXQoKZGVmIGNrKG1pZCwgY250KToKICAgIHdkdCA9IFtdCiAgICBmb3IgejEsejIsejMgaW4gYWR0OgogICAgICAgIHdkdC5hcHBlbmQoejIgLSB6MyAqIG1pZCkKICAgIHdkdC5zb3J0KHJldmVyc2UgPSBUcnVlKQogICAgcmV0dXJuIHN1bSh3ZHRbOmNudF0pID49IDAKCmRlZiBkaXNwKG1pZCwgY250KToKICAgIHdkdCA9IFtdCiAgICBmb3IgaXgsIHogaW4gZW51bWVyYXRlKGFkdCk6CiAgICAgICAgd2R0LmFwcGVuZChbelsxXSAtIHpbMl0gKiBtaWQsIGl4LCB6WzFdLHpbMl1dKQogICAgd2R0LnNvcnQocmV2ZXJzZSA9IFRydWUpCiAgICBzbXAsIHNtYSwga3NpID0gMCwgMCwgMAogICAgZm9yIHEgaW4gd2R0WzpjbnRdOgogICAgICAgIGtzaSB8PSAxPDxxWzFdCiAgICAgICAgc21wICs9IHFbMl0KICAgICAgICBzbWEgKz0gcVszXQogICAgcHJpbnQoZiJ7c21wIC8gc21hOi42Zn3kurova20yKVxuIFsiLCBlbmQ9IiAiKQogICAgZm9yIGkgaW4gcmFuZ2UoNDcpOgogICAgICAgIGlmIGtzaT4+aSAmIDE6IHByaW50KGFkdFtpXVswXSwgZW5kPSIgIikKICAgIHByaW50KCJdIikKCmRlZiBmbmMoY250KToKICAgIG9rICwgbmcgPSAwLjAsIDEwMDAwLjAKICAgIGZvciBxIGluIHJhbmdlKDEwMCk6CiAgICAgICAgbWlkID0gKG9rICsgbmcgKSAvMi4wCiAgICAgICAgaWYgY2sobWlkLCBjbnQpIDogb2sgPSBtaWQKICAgICAgICBlbHNlOiBuZyA9IG1pZAogICAgI3ByaW50KG9rKQogICAgZGlzcChvaywgY250KQoKCmZuYygyMCkK