#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

vector <vector <int> > triangle_structure(500,vector<int> (500,-1)); 
int count_l=0; 

bool isPrime(int num){
    if (num <= 3) {
        return num>1;
    }
    if (num % 2 == 0 || num % 3 == 0) {
        return false;
    }
    for (int i = 5; i * i <= num; i = i + 6) {
        if (num % i == 0 || num % (i + 2) == 0)
            return false;
    }
    return true;
}


void create_triangle(){
    fstream inputFile("data.txt");
    string line;

    int count_w=0;
    while(getline(inputFile,line)){
        string words;
        stringstream ss(line.c_str());
        while(getline(ss,words,' ')) {
            if(!isPrime(stoi(words))) {
                triangle_structure[count_l][count_w] = stoi(words);
            }
            else{
                triangle_structure[count_l][count_w] = -1;
            }
            count_w++;
        }
        count_w=0;
        count_l++;
    }
}


int main() {

    create_triangle();

    bool fullPrimeLine=true; 

    for(int i=count_l-2;i>=0;i--) {
        for(int j=0;j<count_l;j++) {

            int* root = &triangle_structure[i][j];
            int* leftChild = &triangle_structure[i+1][j];
            int* rightChild = &triangle_structure[i+1][j+1];

            if(*root != -1){

                if(*leftChild>*rightChild){
                    *root = (*root)+(*leftChild);
                }
                else if (*rightChild>*leftChild){
                    *root = (*root)+(*rightChild);
                }
                else{
                    if(*rightChild != -1){
                        *root = (*root)+(*rightChild);
                    }
                    else{
                        for(int k=0;k<count_l; k++){
                            if(triangle_structure[i][k]!=-1){
                                fullPrimeLine=false;
                                break;
                            }
                        }

                        if(fullPrimeLine==false) {
                            *root = -1;
                        }
                    }
                }
            }
        }
        fullPrimeLine=true;
    }

    cout<<"Max sum is: "<<triangle_structure[0][0]<<endl;


    return 0;
}