With a brute force program solver written in C#, I found a solution with sum 366:

        3 11  5 | 19
       37 17 13 | 67
        7 31 23 | 61
       ---------+---
    29 47 59 41 | 43

I let the program run until the top left corner was 61, so I'm pretty sure that there are no better solutions, but feel free to look for yourself:

[Source code at PasteBin][1] (you might want to change the initial value of `recordSum` to something bigger than 366 to actually get some results).


  [1]: http://pastebin.com/dPJ6ahuS